동적 프로그래밍 : 동전(백준 9084번)

▶ 문제 : https://www.acmicpc.net/problem/9084

9084번: 동전

##### 문제 #####
# 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 
# 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 
# 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

##### 입력 #####
# 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 
# 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 
# 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 
# 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 
# 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.
# 편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

##### 출력 #####
# 각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 
# 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

 

▶ 접근 방법

점화식을 발견하기 쉽지 않았다.
우선, 1부터 목표 금액까지의 리스트를 만들었다.
동전 세트에서 동전을 하나 꺼내 앞선 리스트 범위 내의 금액을 만들 수 있는 경우를 찾았다.
이후 다음 동전을 꺼내 앞선 과정을 반복하였는데,
다음 동전으로 리스트 범위 내의 금액을 만드는 경우의 수는
이전 동전으로 수행했던 결과를 포함해야 한다.

동전과 목표 금액을 작은 숫자로 하여 직접 하나 씩 해보는 것이 보다 이해에 도움이 되었다.

 

▶ 풀이 코드

import sys

num_of_test = int(sys.stdin.readline().rstrip())

for _ in range(num_of_test):
    num_of_coin = int(sys.stdin.readline().rstrip())
    coins = list(map(int, sys.stdin.readline().split()))
    target_price = int(sys.stdin.readline().rstrip())
    
    # 목표 금액 만큼 리스트를 만들어준다.
    case = [0] * (target_price + 1)
    case[0] = 1

    # coin을 하나씩 꺼내보면서
    for coin in coins :
        # 1부터 목표 금액 중 꺼낸 coin보다 큰 금액이 있다면
        for i in range(1, target_price + 1):
            if i >= coin:
                # 그 금액에서 coin을 뺀 금액을 만들 수 있는 가지 수를 더해준다.
                case[i] += case[i - coin]
    print(case[target_price])

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)

2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : LCS(백준 9251번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)