흙금이네 블로그

아이디어 #1 동적 계획법으로 사용하는 동전의 최소 개수를 구한다. 풀이 #1 k+1로 초기화된 k+1 길이의 리스트를 dp를 생성한다. 차례로 입력 받은 동전의 가치 c가 k보다 크거나 중복되는 동전인 경우 continue로 건너뛰고, 아니면 dp[c]에 1을 저장한다. c보다 큰 가치 합들에서 각각 c를 뺀 가치 합의 사용 동전 최소 개수보다 1 큰 값과 비교해 dp의 최솟값을 갱신한다. 가치 합을 k로 만들 수 있으면 사용하는 동전의 최소 개수를 출력하고, 그렇지 않으면 -1을 출력한다. import sys input = sys.stdin.readline def solution(): n, k = map(int, input().split()) dp = [k+1]*(k+1) for _ in range(..