흙금이네 블로그

아이디어 임의의 수 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[..

아이디어 오일러 피 함수로 n과 서로소인 n 이하의 자연수 개수를 구한다. 풀이 #1 (Python) 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다. 자연수 \(n\)이 어떤 소수 \(p\)를 소인수로 갖는다면 \(n\) 이하인 \(p\)의 배수는 \(n\)과 서로소가 아니다. \(n\)을 구성하는 소인수 \(p\) 외의 다른 소인수들의 곱을 \(a\)라 할 때, \(n\) 이하인 \(p\)의 배수는 \(\frac{ap^{m}}{p}=ap^{m-1}\)개 존재한다. n과 서로소가 아닌 n 이하의 자연수의 개수를 구하면 조건을 만족하는 k의 개수를 구할 수 있다. 초기값이 n인 결과값을 차례로 이전 소인수들의 배수가 아닌 현재 소인수의 배수의 개수만큼 감소시켜 나간다. 지금 풀이도 어렵긴 하지만 ..

아이디어 그리디 알고리즘으로 참가할 수 없는 대회가 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():..