[백준 2293번] 동전 1 (Python)

문제 링크

[백준 2293번] 동전 1

 

문제 요약

n가지 종류의 동전으로 합이 k원이 되는 경우의 수 구하기

 

접근 방법 정리

DP를 풀 때 중요하다고 강조했던 2가지를 생각해서 접근한다.

1. 큰 문제를 작은 문제로 나눠 작은 문제의 합으로 풀 수 있는지를 고민해야하고

2. 동일한 작은 문제를 반복적으로 해결할 수 있는지 고민

 

1번에 해당하는 것은 합이 k원을 구하는 큰 문제에서 각 금액을 만들 수 있는 경우의 수를 차례대로 계산해나가는 것이다.

2번에 해당하는 것은 1번으로 구해놓은 정보를 바탕으로 반복문을 수행해 DP 배열을 업데이트 한다.

 

코드

n, k = map(int, input().split())
nums = [int(input()) for _ in range(n)]
dp = [0 for i in range(k + 1)]
dp[0] = 1

for i in nums:
    for j in range(i, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]

print(dp[k])

 

 

구현 자체가 생각이 되지 않아 검색 후 이해한 코드..!

사실 코드를 보고도 이해가 어려웠는데, 다른 분이 블로그에 적어두신 표를 자세히 보니까 이해가 되었다..!

 

dp[j] += dp[j - 1]의 코드를 이해하기 위해 하나만 예를 들어보겠다.

i가 2이고 j가 5일때라면, dp[5] += dp[5 - 2]가 되는데

dp[3]이 만들어졌던 경우에서 2를 더하면 5가 되는 경우의 수를 구할 수 있는 것이다.