[백준2293번] 동전 1 / Python3

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

예제 입력 1

3 10
1
2
5

예제 출력 1

10

나의 풀이

dp문제를 여러개 풀어보긴 했지만 아직 점화식 세우는게 익숙하지 않다고 느끼게 해준 문제이다. 우선 이 문제는 검색을 통해 점화식을 찾아냈다...

다른 동전 문제들과 다르게 이 문제는 여러 개의 동전이 주어지고 모든 경우의 수를 구하는 문제였다. 그래서 n개의 동전이 있다면 1개만 사용할때부터 n개를 사용할때까지의 개수들을 구해나가면 되는 문제였다.

설명하기에 앞서 점화식부터 써놓아보겟다.

dp[i,k] = dp[i-1,k]                              ( if k < c )
                    dp[i-1,k] + dp[i-1,k-c]  ( if k >= c )

문제에서 주어진 예제를 가지고 2차원 배열로 이 문제를 그려보면 다음과 같다.

그림과 점화식을 잘 생각해보면서 직접 다시 써보다보면 이해가 갈 것이다. 간단히 말로 설명하면 동전의 금액이 k원보다 작으면 이전 동전까지 사용할때의 개수를 그대로 가지고 가면되고, 동전의 금액이 k원과 같거나 크다면 k에서 현재 동전 금액의 동전 하나를 뺀 상황에서의 개수를 더해주면 된다. 위의 그림에서 파란색으로 그려진 것이 그것을 나타낸 것이다.

점화식을 알고나면 코드를 짜는 것은 어렵지 않다 그러나 문제에서 메모리크기를 작게 주었기 때문에 2차원 배열로는 풀 수가 없다. 그래서 k+1크기의 배열 하나만을 사용해서 이 문제를 풀 수 있다. 왜냐하면 점화식에서 보면 k < c일 경우 값을 변경하지 않으면 되고, k >= c일 경우 이미 앞에서 구해논 값과 현재 위치에서의 값을 사용하면 되기때문이다. 따라서 이렇게 메모리 문제도 해결할 수 있다.

코드

# 2293번 동전 1
import sys

# main
n, k = [int(x) for x in sys.stdin.readline().split()]

coin = []
for _ in range(n):
    coin.append(int(sys.stdin.readline()))

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

print(dp[k])