[BOJ][Python][실1][9084] 동전

문제 링크

문제링크

첫 번째 풀이

dp[i] : i원을 채우는 모든 경우의 수

동전이 1원짜리, 2원짜리 두 개가 있을 때 10원을 채우는 과정을 생각해보겠습니다. 0원을 동전으로 채우는 방법의 수를 1개로 정의합니다. 이후에 dp[i] (i원을 동전으로 채우는 방법)을 구하기 위한 방법은 두 가지로 나뉩니다.

1. 0원을 채우는 방법은 아무 동전도 안쓰는 1가지뿐 : dp[0] = 1
2. i-1원을 이미 채운 상태에서 1원짜리 동전을 더해서 i원을 채우는 경우 dp[i] += dp[i-1]
3. i-2원을 이미 채운 상태에서 2원짜리 동전을 더해서 i원을 채우는 경우 dp[i] += dp[i-2]

그런데 주의할 점은 1원짜리로 채울 수 있는 모든 경우를 구한 뒤, 여기에 2원짜리를 추가해서 채울 수 있는 경우의 수를 더해야합니다.

# 올바른 경우
for coin in coins:
    for i in range(m - coin + 1):
        dp[i + coin] += dp[i]
# 올바른 경우 2
for c in coin:
    for m in range(1, M + 1):
        if m - c >= 0:
            ans[m] += ans[m-c]

# 틀린 풀이
for i in range(m):
    for coin in coins:
        if i + coin <= m:
            dp[i + coin] += dp[i]

올바른 경우를 카운트 했을 때는 아래와 같은 표로 생각할 수 있습니다.

dp[i]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
초기값	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
5	1	1	1	1	1	2	2	2	2	2	3	3	3	3	3	4	4	4	4	4	5
10	1	1	1	1	1	2	2	2	2	2	4	4	4	4	4	6	6	6	6	6	9

틀린 풀이로 작성하는 경우 중복된 카운트가 생깁니다.

아래 각 cell의 (a,b,c)는 1원짜리가 a개, 5원짜리가 b개, 10원짜리가 c개인 경우를 나타냅니다.

# 틀린 풀이
for i in range(14):
    for coin in [1,5,10]:
        if i + coin <= m:
            dp[i + coin] += dp[i]
'''
실행결과 print(dp)
[1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0]
[1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 2, (*3), 1, 1, 1, 3, 1, 1, 1, 1]
'''

위 실행 결과에서 (*3) 위치가 아래 표에서 ????의 위치입니다. 6을 동전으로 나타내는 방법은 두 가지 방법뿐인데 3이됩니다. 그 이유는 dp[5]에는 (0,1,0)과 (5,0,0)가 모두 들어있고, 여기에 1원이 추가되면서 (1,1,0)과 (6,0,0)이 더해지는데 이미 (1,1,0)은 존재하기 때문에 중복이 발생하고 (*3)이 생긴 것입니다.

dp[i]	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
초기값	0,0,0
(1,5,10)		1,0,0				0,1,0					0,0,1
			2,0,0				1,1,0					1,0,1
				3,0,0				2,1,0					2,1,1
					4,0,0				3,1,0					3,1,1
						5,0,0				4,1,0					4,1,1
							?????

정답 코드

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import Counter, deque
from copy import deepcopy

# sys.stdin = open("input.txt", "r")

tc = int(input())
for _ in range(tc):
    dp = [0] * 10010
    n = int(input())
    coins = list(map(int, sys.stdin.readline().split()))
    m = int(input())
    dp[0] = 1
    for coin in coins:
        for i in range(m - coin + 1):
            dp[i + coin] += dp[i]
    print(dp[m])

Success Notice: 수고하셨습니다.