[백준 파이썬] 2293 동전 1

📌문제 출처

백준 단계별 문제풀이 - 동적 계획법 2
https://www.acmicpc.net/problem/2293

2293번: 동전 1

❓ 문제

❗ 풀이

• dp 활용

📗 풀이 코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
coins = [int(input()) for _ in range(n)]
dp = [0]*(k+1)
dp[0] = 1 # 0으로 0을 만드는 방법 1가지 추가, 이걸 지정해줘야 첫번째 동전이 들어올 때 가지수 추가 가능
for coin in coins : # 동전을 한 종류씩 꺼내서
    for i in range(coin,k+1): # 해당 동전이 추가될 수 있는 가치의 범위(해당 동전 가치~k)
        dp[i] += dp[i-coin]
print(dp[-1])

📗 코드 해설

• 동전 종류를 하나씩 추가하며 0부터 k까지의 가치를 만들어보자.
• 예제처럼 10의 가치를 만들어야하고 동전 종류는 1원, 2원, 5원이 있다고 하자.
• 동전이 없을 때는 0의 가치만 한가지 방법으로 만들 수 있다.
  따라서 이 때 dp = [0] * (k+1); dp[0] = 1
• 1원을 가지고 가치를 만들어보자. 0원으로 만들 수 있는 가치에 1원을 하나씩 추가한다고 생각해보면
  1의 가치의 경우 : 0원으로 만든 0의 가치(1가지 방법) + 1원 동전 하나 추가 => 1가지 경우 추가
  2의 가치의 경우 : ↑에서 만든 1의 가치(1가지 방법) + 1원 동전 하나 추가 => 1가지 경우 추가
  이런 식으로 10까지의 가치를 채울 수 있다.
• 2원을 가지고 가치를 만들어보자. 0원과 1원으로 만들 수 있는 가치에 2원을 하나씩 추가한다고 생각해보면
  (앞으로 0원은 생략)
  0,1의 가치의 경우 : 2원 동전을 추가할 수 없으므로 그대로 유지
  2의 가치의 경우 : 앞서 만든 0의 가치(1가지 방법) + 2원 동전 하나 추가 => 1가지 경우 추가
  3의 가치의 경우 : 앞서 만든 1의 가치(1가지 방법) + 2원 동전 하나 추가 => 1가지 경우 추가
  4의 가치의 경우 : 앞서 만든 2의 가치(2가지 방법) + 2원 동전 하나 추가 => 2가지 경우 추가
  이런 식으로 10까지의 가치를 채울 수 있다.
• 5원을 가지고 가치를 만들어보자. 1,2원으로 만든 가치에 5원을 하나씩 추가해보자.
  0~4 가치의 경우 : 5원 동전을 추가할 수 없다.
  5의 가치의 경우 : 앞서 만든 0의 가치(1가지 방법) + 5원 동전 하나 추가 => 1가지 경우 추가
  6의 가치의 경우 : 앞서 만든 1의 가치(1가지 방법) + 5원 동전 하나 추가 => 1가지 경우 추가
  7의 가치의 경우 : 앞서 만든 2의 가치(2가지 방법) + 5원 동전 하나 추가 => 2가지 경우 추가
• 아래와 같은 방법으로 원래 있던 가치를 만드는 방법에 동전을 하나씩 추가하면서 가치를 늘려갈 수 있다.
  dp를 계속 덮어씌우면서 dp[i] = dp[i-coin] + dp[i]로 초기화를 해줄 수 있다.