백준 9084번 : 동전 in Python

9084번: 동전

 

www.acmicpc.net

이 문제는 동전의 종류가 주어질 때 주어진 금액을 만드는 모든 방법의 수를 구하는 문제이다.

특히 이 문제는 이전의 1, 2, 3 더하기 3 문제와 어떤 주어진 자연수를 특정 수의 합으로 나타내는 방법의 수를 구한다는 면에서 비슷하다. 다만, 이전 문제의 경우 같은 개수의 수를 사용하더라도 더하는 순서가 바뀌는 경우 다른 방법으로 취급했는데, 이 문제는 단순히 동전의 개수로만 방법의 수를 따지기에 순서를 고려하지 않는다는 점에서 약간의 차이가 있다.

백준 15988번 : 1, 2, 3 더하기 3 in Python

15988번: 1, 2, 3 더하기 3 www.acmicpc.net 이 문제는 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 이때 정수를 1, 2, 3의 합으로 표현할 때 1, 2, 3의 개수가 같고 더하는 순서만 다른 방법..

wanna-be-developer-yjh.tistory.com

그렇다면 이 문제는 어떻게 해결할 수 있을까? 이제는 동전의 개수로만 방법의 수를 따지기에, 각 동전에 대해 그 동전이 포함될 경우에 대해 방법의 수를 순차적으로 구해나간다. 예를 들어 동전이 1원짜리, 2원짜리 동전이 주어졌다고 할 때, 우선 1원짜리 동전으로만 1원부터 목표 금액까지 도달할 수 있는 경우의 수를 구한다. 물론 이 경우 모든 경우의 수가 1로 동일할 것이다. 그 다음 여기에 2원짜리 동전을 추가해 2원짜리 동전이 들어갈 경우 방법의 수를 2원부터 목표 금액까지 구한다. 이때 2원짜리 동전을 추가했을 때 j원을 만드는 방법의 수까지 구했다고 하자. 이때 j+2원을 만들기 위해서는 2원짜리 동전을 추가했을 때 j원을 만드는 각 방법에 2원을 추가하면 될 것이다. 그러므로 기존의 j+2원을 만드는 방법의 수에 j원을 만드는 방법의 수를 더하면 된다. 이때 기존에 j+2원을 만드는 방법은 1원짜리 동전으로만 만드는 방법이었다. 이를 j가 (목표 금액-2)원일 때까지 반복하면 2원짜리 동전을 추가했을 때 가능한 방법의 수를 구할 수 있다.

여기서 더하는 순서가 바뀌는 경우가 고려되지 않는 이유는 위 과정을 거칠 때 앞에서 나온 동전부터 차례대로 더하기 때문이다. 예를 들어 목표 금액이 10원일 때 1원짜리 동전을 4개, 2원짜리 동전을 3개 쓰는 경우 우선 1원짜리 동전만 사용하는 경우에 대해 목표 금액이 4원일 때 방법인 1+1+1+1을 구한 뒤, 2원짜리 동전을 사용하는 경우에서 이를 고려해 여기에 2원을 3번 넣어 1+1+1+1+2+2+2라는 방법을 도출해낸다. 여기서 2원을 1원보다 먼저 더하는 경우는 고려되지 않으므로, 항상 더하는 순서가 바뀌는 경우를 고려하지 않게 되는 것이다.

이를 코드로 구현하면 다음과 같다.

T = int(input())
for _ in range(T):
    N = int(input())
    coins = list(map(int, input().split()))
    m = int(input())
    # 주어진 동전으로 각 금액을 만드는 모든 방법의 수를 저장하는 배열
    dp = [0 for _ in range(m+1)]
    # 초기값 설정
    dp[0] = 1
    for coin in coins:
        for j in range(m+1-coin):
            dp[j+coin] += dp[j]
    print(dp[m])