[ BOJ 3067 ] Coins(Python)

uoayop·2021년 5월 26일
1

알고리즘 문제

목록 보기
73/103
post-thumbnail

문제

https://www.acmicpc.net/problem/3067

N가지의 동전 종류가 주어질 때, M원을 만들 수 있는 방법의 수를 구하면 된다.
dp와 그리디 알고리즘을 비교할 때 자주 등장하는 전형적인 문제라고 한다.


문제 풀이

0. 입력 받기

n = int(input())
coins = list(map(int, input().rsplit()))
want = int(input())

1. dp 배열 정의하기

dp = [0 for _ in range(want+1)]
dp[0] = 1

dp[i] = i원 동전을 이용해서 만들 수 있는 방법의 수

0원은 0가지 동전으로 만들 수 있으므로 1가지 방법 뿐이다.
따라서 dp[0] = 1

2. 동전의 종류를 고려해서 dp 할당하기

for i in range(n):
   for j in range(coins[i], want+1):
      dp[j] += dp[j - coins[i]]

동전 종류가 [1, 2, 3]와 같을 때 6원 을 만드는 방법을 생각해보자

i = 0, j = 1~6, coins[i] = 1 일 때

dp[1] += dp[1-1]
dp[2] += dp[2-1]
dp[3] += dp[3-1] ...

i / jdp[0]dp[1]dp[2]dp[3]dp[4]dp[5]dp[6]
01111111

i = 1, j = 2~6, coins[i] = 2 일 때

dp[2] += dp[2-2]
dp[3] += dp[3-2]
dp[4] += dp[4-2] ...

i / jdp[0]dp[1]dp[2]dp[3]dp[4]dp[5]dp[6]
01111111
11122334

i = 2, j = 3~6, coins[i] = 3 일 때

dp[3] += dp[3-3]
dp[4] += dp[4-3]
dp[5] += dp[5-3] ...

i / jdp[0]dp[1]dp[2]dp[3]dp[4]dp[5]dp[6]
01111111
11122334
21123457

dp[6] 을 출력하면 된다.


코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    coins = list(map(int, input().rsplit()))
    want = int(input())

    # dp[i] = i원 동전을 이용해 j원을 만들 수 있는 경우의 수
    dp = [0 for _ in range(want+1)]
    dp[0] = 1

    for i in range(n):
        for j in range(coins[i], want+1):
            dp[j] += dp[j-coins[i]]

    print(dp[want])
profile
slow and steady wins the race 🐢

0개의 댓글