문제

2293 : 동전 1 문제이다.

n가지 종류의 동전을 적당히 사용해서 k원을 만드는 모든 경우의 수를 구한다. 그러나 사용한 동전의 구성이 같은데, 순서가 다른 것은 같은 경우이다.

알고리즘

다이나믹 프로그래밍 문제이다. 왜냐하면

• 전체 문제를 부분 문제로 나눌 수 있다. 즉, 부분 문제의 답을 이용해 전체 문제의 답을 구할 수 있다.

DP의 기법

다이나믹 프로그래밍은 다른 말로 메모이제이션이라고도 한다. 즉, n차원 배열에 부분 문제들의 답을 저장해둔 후, 그 부분 문제들의 답을 이용해서 그 다음 전체 문제의 답을 구한다. 단순히 모든 부분 문제들의 답을 더하거나, 곱하거나 하는 것이 아니라, 이전 부분 문제의 답을 이용해 다음 부분문제의 답을 구한다.

DP는 경험해본 바 두 가지 분류로 나뉘는데,

1. 점화식이 쉽지만 DP에 어떤 것을 어떻게 저장할 지 알아내는 게 어려운 경우
2. 점화식이 어려운 경우

로 나뉘는 것 같다.

해당 문제의 경우에는 1에 해당한다. DP에 어떤 것을 어떻게 저장할지를 정하면, 바로 답을 구할 수 있다.

접근

내 경우 처음에는 다음과 같은 코드로 잘못 작성했었다. DP 배열의 정의를 __K원을 만드는 경우의 수__로 설정했으며, 이전 코인 조합 중에 N번째 종류의 코인을 더했을 때 K원이 나오는 경우를 DP에 담아주었다.

코드는 다음과 같다.

dp[0] = 1 # Base Condition
for goalCoinSum in range(1,k+1) :
	for coin in coins :
        if(goalCoinSum >= coin) :
            dp[goalCoinSum] += dp[goalCoinSum-coin]

이렇게 할 경우 예제의 답에 비해, 굉장히 많은 경우의 수를 얻게 된다. 왜 그런지 곰곰히 생각해보니 내 접근법은 순서 중복을 허용하고 있었다.

k원을 만드는 경우를 각 코인 종류를 순회하며 살피고 있다. 이걸 예제를 기반으로 조합으로 풀어서 보면 다음과 같은 결과가 나온다.

dp[1] : dp[1-1] = (1)

dp[2] : dp[2-1] + dp[2-2] = (1,1) + (2)

dp[3] : dp[3-1] + dp[3-2] = (1,2) (1,1,1) + (2,1)

dp[4] : dp[4-1] + dp[4-2] = (1,2,1)(1,1,1,1)(2,1,1) + (1,1,2)(2,2)

dp[5] : dp[5-1] + dp[5-2] + dp[5-5] = (1,2,1,1)(1,1,1,1,1)(2,1,1,1)(1,1,2,1)(2,2,1) + (1,2,2)(1,1,1,2)(2,1,2) + (5)

…

위처럼 결국 조합 중복이 있는, 즉 순서가 있는 조합을 만들어내고 있었다. 우리가 구해야하는 DP배열은 예제로 풀어서 보면 다음과 같다.

dp[1] : (1)

dp[2] : (2) (1,1)

dp[3] : (2,1) (1,1,1)

dp[4] : (2,1,1) (1,1,1,1) (2,2)

dp[5] : (2,1,1,1) (1,1,1,1,1) (2,2,1) (5)

그렇다면 이걸 어떻게 구해야할까? 답은 순서를 강제해주는 것이다. [1,2,5] 배열이라면 1보다 2는 뒤에, 2보다 5는 뒤에 붙게끔 고려해준다. 이를 위해서는 coin 배열을 먼저 순회하고, 안쪽 루프에서 k원을 만드는 경우를 구해준다.

즉, 1원이 1~k원이 되는 경우를 모두 구해주고, 그 다음에 2원이 1~k원이 되는 경우를 모두 구해주고, 그 다음에는 5원이 1~k원이 되는 경우를 모두 구해준다.

결국 정답 전체코드는 다음과 같다.

정답코드

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0]*(k+1)
dp[0] = 1
for coin in coins :
    for goalCoinSum in range(1,k+1) :
        if(goalCoinSum >= coin) :
            dp[goalCoinSum] += dp[goalCoinSum-coin]
print(dp[k])