흙금이네 블로그

아이디어 BFS로 수의 한 자리만 숫자를 바꾼 다른 소수로 변환해 나가며 변환에 필요한 최소 횟수를 구한다. 풀이 #1 (Python) import sys input = sys.stdin.readline def solution(): P = [True]*10000 for i in range(2, 101): if P[i]: for j in range(i*2, 10000, i): P[j] = False for i in range(1000): P[i] = False T = int(input()) for _ in range(T): A, B = map(int, input().split()) visited = [0]*10000 visited[A] = 1 queue = [A] while queue: num = queu..

아이디어 DP로 완전순열을 구한다. 풀이 #1 (Python) 점화식을 구하기 위해 임의로 학생과 기숙사에 번호를 매기고, 1번 학생이 K번 기숙사에 배정되는 경우를 고려한다. K번 학생이 1번 기숙사에 배정되는 경우의 수는 1번 학생과 K번 학생을 제외하고 학생 수가 N-2인 경우의 수와 같다. K번 학생이 1번 기숙사에 배정되지 않는 경우의 수는 1번 학생을 제외하고 학생 수가 N-1인 경우의 수와 같다. K는 1을 제외한 N-1개의 수가 가능하므로 두 경우의 수를 더하여 N-1만큼 곱하면 학생 수가 N인 경우의 수를 구할 수 있다. import sys input = sys.stdin.readline def solution(): T = int(input()) dp = [0]*21 dp[2] = 1 f..

아이디어 학생 수의 공약수와 그 공약수의 개수의 곱의 최댓값을 구한다. 풀이 #1 (Python) 2부터 값을 차례로 증가시키면서 현재 수와 현재 수의 배수가 되는 학생 수 개수 곱의 최댓값을 갱신해 나간다. def solution(): N = int(input()) students = tuple(map(int, input().split())) M = max(students) multiples = [0]*(M+1) for student in students: multiples[student] += 1 res = N for d in range(2, M+1): cnt = sum(multiples[d:M+1:d]) if cnt > 1 and d*cnt > res: res = d*cnt print(res) so..

아이디어 임의의 수 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인 결과값을 차례로 이전 소인수들의 배수가 아닌 현재 소인수의 배수의 개수만큼 감소시켜 나간다. 지금 풀이도 어렵긴 하지만 ..