[Python/백준] 2294 동전 2

https://www.acmicpc.net/problem/2294

2294번: 동전 2

<문제 해설>

다이나믹 프로그래밍 문제이다. 해결 방법은 1원부터 k원까지 모든 가격당 필요한 최소 동전개수를 순서대로 구하면 된다. 이때 최소 동전 개수를 구하는 법은 k원에서 동전의 가치를 빼주고 남은 가치의 최소 동전 개수와 1을 더하면 k원의 최소 동전 개수가 된다(예시를 참고하면 더 쉽게 이해할 수 있다.). 모든 동전 종류당 한번씩 위 방식을 사용해주고 이중 최소 개수를 k원 개수에 저장하면된다.  초기 개수를 99999로 정해줘서 이보다 작은 값이면 개수에 저장될 수 있게 했다. 구할수 없는 가치의 합인경우 개수가 변하지 않아서 99999임으로 출력할때 개수가 99999면 -1로 출력하도록 한다.

<예시>

입력 : 2 5

          2

          3

1원

1원은 동전들로 만들 수 없음으로 99999개수로 남는다

2원

2원은 가치가 2인 동전하나를 사용하면 되니 1이된다.

3원

3원은 동전들로 만들 수 없음으로 99999가 남는다.

4원

4원은 가치가 2인 동전 2개를 사용하면 되니 2가 된다.

5원

5원은 가치가 2인동전 한개 3인동전 한개를 사용하면 되니 2가된다.

output : 2

<코드>

N,K = list(map(int,input().split()))

coins = []

for i in range(N):
    coins.append(int(input()))
    
dp = [99999]*(K+1)
dp[0] = 0
for i in range(1,K+1):
    for coin in coins:
        if coin <= i:
            if dp[i] > 1 + dp[i - coin]:
                dp[i] = 1 + dp[i - coin]

if dp[K] == 99999:
    print(-1)
else:
    print(dp[K])

<코드 설명>

N,K = list(map(int,input().split())) //N, K를 정수로 받아오기

coins = [] //동전들의 값어치를 저장할 배열

for i in range(N):
    coins.append(int(input())) //동전의 값어치를 입력받아온다.
    
dp = [99999]*(K+1) //초기값을 99999로한 각 원당 개수를 저장할 배열
dp[0] = 0 //0원을 만들방법은 항상 0이니 0을 저장
for i in range(1,K+1): //1부터 K원까지 i에 넣으면서
    for coin in coins: //coins에서 동전들을 coin으로 빼주면서
        if coin <= i: //만약 coin이 i원보다 크면 계산할 필요도 없고 배열에 넣으면 indexerror가 나오니 제외
            if dp[i] > 1 + dp[i - coin]: //coin(개수 1) + dp[i - coin](i에서 coin을 뺀 원의 개수)가  원래 저장값보다 작으면
                dp[i] = 1 + dp[i - coin] //개수 변경

if dp[K] == 99999: //초기값으로 저장되있으면 값을 구할수 없다는 뜻이니
    print(-1) //-1 출력
else: //아니면
    print(dp[K]) //dp[K] 에 저장된 개수 출력