전체 글 (171) 썸네일형 리스트형 [BOJ] [Python] 15686번 : 치킨 배달 문제를 정리해보자. 도시 : N x N 빈칸 : 0 집 : 1 치킨집 : 2 도시의 칸 : (r, c) (각각 1부터 시작한다.) 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리 도시의 치킨 거리 : 모든 집의 치킨 거리의 합 거리 계산 : | r1 - r2 | + | c1 - c2| 가장 수익을 많이 낼 수 있는 치킨집의 개수, 최대 M개를 이용하여 도시의 치킨 거리의 최솟값을 출력하면 되는 문제이다. 먼저, 최대 M개를 선택해야 하는 점에 주목하자. 치킨집은 M개를 제외하고는 모두 폐업시킬 것이다. 완전탐색으로 생각하자면, 치킨집이 M개되는 모든 경우의 수를 따져주면 된다. n, m = map(int, input().split()) chicken = [] house = [] dp = [[0] * .. [BOJ] [Python] 14502번 : 연구소 문제를 정리해보자. 연구소 : N x M 빈칸 : 0 ( 3개 이상 ) 벽 : 1 바이러스 : 2 ( 2개 이상, 10개 이하 ) 세울 수 있는 벽의 수 : 3개 (꼭 3개를 세워야 한다.) 벽을 3개 세운 뒤, 안전 영역의 크기의 최댓값을 구하는 문제이다. 바이러스는 bfs로 퍼트려주면 된다. 그 전에, 벽은 어떻게 세워야 할까? 벽을 세울 수 있는 모든 경우의 수를 탐색하면 된다. 먼저 bfs를 제외한 make_wall 코드를 보자. 재귀 함수를 이용해서 모든 경우의 수를 볼 것이다. 벽의 개수는 count 개수이고, 3개가 될 때까지 만들어준다. import sys from collections import deque input = sys.stdin.readline s = [] dx = [0, 0,.. [BOJ] [Python] 2960번 : 에라토스테네스의 체 소수의 배를 제거하면서 k번째를 찾으면 된다. dp 리스트로 중복방지를 하며, K번째를 찾을 수 있게 카운트해 줬다. 예를 들어, 6은 2의 3의 공통배수이다. 따라서 중복제거를 피해야 한다. import sys, math input = sys.stdin.readline n, k = map(int, input().split()) sosu = [] for num in range(2, n + 1): check = True for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: check = False break if check: sosu.append(num) def main(): cnt = 0 dp = [0] * (n + 1) for num in sosu.. 이전 1 ··· 39 40 41 42 43 44 45 ··· 57 다음