흙금이네 블로그

아이디어 DP로 사탕 가격의 합에 대한 경우의 수를 구해 나가고, 에라토스테네스의 체로 가격 합이 소수인지 확인한다. 풀이 #1 (Python) dp[i]는 가격 합이 i인 사탕을 사는 방법의 수를 나타낸다. import sys input = sys.stdin.readline def solution(): N = int(input()) candies = dict() total = 0 zero = 1 for _ in range(N): price = int(input()) if price: candies[price] = candies.get(price, 0)+1 total += price else: zero += 1 P = [1]*(total+2) P[0] = P[1] = 0 for i in range(2, ..

아이디어 누적 합으로 가치 합이 최대가 되는 구간을 찾는다. 풀이 #1 (Python) 차례로 현재 인덱스보다 M 작은 인덱스까지 누적 합이 최소가 되는 인덱스를 찾고, 해당 인덱스부터 현재 인덱스까지 구간 합의 최댓값을 결과값으로 갱신해 나간다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) prefix_sum = [0]*(N+1) for i in range(1, N+1): prefix_sum[i] = prefix_sum[i-1]+int(input()) res = min_val = 0 for i in range(M, N+1): if prefix_sum[i-M] < min_val: min_val ..

아이디어 #1 맵을 이용하여 이동 가능한 좌표를 찾아 BFS하여 최소 이동 횟수를 구한다. 풀이 #1 (Python) 파이썬에서는 딕셔너리로 맵을 이용할 수 있다. import sys input = sys.stdin.readline def solution(): n, T = map(int, input().split()) pos = dict() for _ in range(n): x, y = map(int, input().split()) pos[(x, y)] = -1 queue = [(0, 0)] while queue: x, y = queue.pop(0) if y >= T: print(pos.get((x, y), 0)) return for nx in range(x-2, x+3): for ny in range(..