흙금이네 블로그

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