[2293] 동전1

백준 2293번 동전1

n, k = map(int, input().split())
c = []
dp = [0 for i in range(k + 1)]
dp[0] = 1
for i in range(n):
    c.append(int(input()))
for i in c:
    for j in range(1, k + 1):
        if j - i >= 0:
            dp[j] += dp[j - i]
print(dp[k])

핵심 아이디어

k길이의 배열을 만들고, 각 원소 별 경우의 수를 계산하여 k가 되는 경우의 수를 구한다.

 

설명

dp 배열에서 원소를 dp[key] = value 라고 한다면,

• key : 1, 2, 3, ... k
• value : key를 만들 수 있는 경우의 수

 

예를 들어 [1, 2, 5] coin을 가지고 k = 4라면, 우리는 약간의 계산으로 경우의 수가 3개인 걸 알 수 있는데, 코드로 보면

• i = 1, j = 1 일 때, $j - i ≥ 0$이므로 $dp[1] += dp[0]$ 이 된다. 이 때 dp[0]은 1이므로 dp[1]도 1이다.  
• i = 1, j =2,3,4일 때도 모두 j - i ≥ 0이므로 dp[2], dp[3], dp[4] 역시 모두 1이다.
• i =2, j = 2 일 때, j - i ≥ 0이므로 dp[2] += dp[0] 이 된다. dp[2]는 2이다. 왜냐하면 누적값이기 때문에
• i = 2, j =3 일 때, j -i ≥ 0이므로, dp[3] += dp[1]에서 dp[1]은 1이므로, dp[3]도 1이다.
• i = 2, j = 4일 때, j - i ≥0이므로, dp[4] += dp[2]에서 dp[2]는 2이므로 dp[4]도 3이다. 왜냐하면 dp[4]가 앞서 1이었기 때문에

 

이로써 dp[4] = 3이므로, 경우의 수가 3개가 나온다.