흙금이네 블로그

아이디어 임의의 수 K를 중심으로 양쪽으로 누적된 두 최대공약수의 최대공약수의 최댓값을 구한다. 풀이 #1 (Python) 누적 합 알고리즘과 비슷한 원리로 합이 아닌 최대공약수를 누적해 리스트에 저장해 나간다. import sys input = sys.stdin.readline def solution(): def gcd(a, b): if a > b: a, b = b, a while a: r = b%a b, a = a, r return b N = int(input()) numbers = tuple(map(int, input().split())) gcd_list = [0]*N gcd_list[1] = numbers[0] res = idx = -1 for i in range(1, N-1): gcd_list[..

아이디어 누적 합으로 가치 합이 최대가 되는 구간을 찾는다. 풀이 #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 ..