[백준][python]2993 동전

문제

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

소스코드

import sys

if __name__ == "__main__":
    n,k = map(int,input().split())
    coin = [int(input()) for _ in range(n)]
    dp = [0] * (k+1)
    dp[0] = 1 

    for c in coin:
        for i in range(c,k+1):
            dp[i] += dp[i-c]

    print(dp[k])

설명

DP 문제이다.

bottom-up 방식으로 문제를 작게 분해하여 답을 구한 후, 작은 답을 이용하여 큰 답을 완성시킨다.

 

여기서 구해야할 값, 메모이제이션 해야할 값은 값을 만들 수 있는 경우의 수이다.

 

주어진 동전을 가지고 값을 만드는 경우를 생각해보면 다음과 같다.

K = 1	K = 2	K = 3	K = 4	K = 5
1	1+1	1+1+1	1+1+1+1	1+1+1+1+1
	2	2+1	2+1+1+1	2+1+1+1
			2+2	2+2+1
				5

(내가 구하고자 하는 값) - (주어진 동전) 을 모두 더하면 내가 구하고자 하는 값을 만드는 경우의 수를 모두 구할 수 있다.

예를 들어 K = 4 인 경우를 생각해보자

- 1 동전을 기준으로 만드는 경우

dp[4 - 1] = dp[3] : 3을 만드는 경우에 1을 붙여서 4를 만들 수 있다 (위의 표 참조) 

 

- 2 동전을 기준으로 만드는 경우

dp[4 - 2 ] = dp[2] : 2을 만드는 경우에 2을 붙여서 4를 만들 수 있다.

 

기준점을 주어진 동전을 기준으로 만들 수 있는 값을 체크해준다.

기준점을 주어진 동전으로 하지 않고 그냥 값으로 체크한다면 반례가 발생한다. 

예를 들어 3 을 만들기 위해 3을 기준으로 동전을 체크한다고 생각해보자.