흙금이네 블로그

아이디어 그리디 알고리즘으로 참가할 수 없는 대회가 1개 이하인지 확인한다. 풀이 #1 (Python) total에는 현재까지 모은 상금 합을 저장하고, max_p에는 현재까지의 상금 최댓값을 저장한다. 상금 합이 상금 상한을 넘기면 flag 값을 1로 저장하고 상금이 max_p인 대회에 참가하지 않았던 것으로 한다. 만약 max_p를 뺀 상금 합이 상금 상한을 넘기면 flag 값을 2로 저장하고 해당 대회에 참가하지 않은 것으로 한다. 두 번 이상 상금 상한을 넘기면 flag 값이 1이면서 max_p를 뺀 상금 합도 상한을 넘기는 경우나 flag 값이 2인 경우 참가할 수 없는 대회 수가 2개 이상이 된다. import sys input = sys.stdin.readline def solution():..

아이디어 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 ..