[정글 알고리즘] - [중] 백준9084- 동전- 골드5

코인 하나를 반영할 때마다 배열이 어떻게 바뀌는지 보여주는 상세형 정리다.

1. 문제를 아주 짧게 말하면

주어진 동전들로 목표 금액 M을 만드는 모든 방법 수를 구하는 문제다. 최소 동전 개수가 아니라 조합의 개수를 세는 것이 핵심이다. [Source](https://www.acmicpc.net/problem/9084)

2. 핵심 아이디어

dp[x]의 뜻

금액 x를 만드는 방법의 수

• 초기값: dp[0] = 1
• 업데이트: dp[money] += dp[money-coin]
• 동전이 바깥 루프여야 순서만 다른 경우를 중복 계산하지 않는다.

3. 전체 코드

1import sys

2

3input = sys.stdin.readline

4t = int(input())

5

6for _ in range(t):

7 n = int(input())

8 coins = list(map(int, input().split()))

9 target = int(input())

10

11 dp = [0] * (target + 1)

12 dp[0] = 1

13

14 for coin in coins:

15 for money in range(coin, target + 1):

16 dp[money] += dp[money - coin]

17

18 print(dp[target])

4. 코드 한 줄씩 설명

줄	코드	설명
3	input = sys.stdin.readline	빠른 입력을 위한 설정이다.
4	t = int(input())	테스트케이스 개수를 입력받는다.
6	for _ in range(t):	현재 테스트케이스의 동전 종류 수를 입력받는다.
7	n = int(input())	동전 금액들을 리스트로 입력받는다.
8	coins = list(map(int, input().split()))	만들어야 하는 목표 금액을 입력받는다.
10		dp[x]는 금액 x를 만드는 방법 수를 뜻한다.
11	dp = [0] * (target + 1)	금액 0은 아무 동전도 쓰지 않는 한 가지 방법이 있으므로 1로 둔다.
13		동전을 하나씩 차례대로 반영한다.
14	for coin in coins:	현재 동전을 써서 만들 수 있는 금액 범위를 순회한다.
15	for money in range(coin, target + 1):	money-coin 금액을 만드는 모든 방법 뒤에 현재 동전을 하나 붙이는 방식으로 방법 수를 누적한다.
17		최종적으로 목표 금액을 만드는 조합의 개수를 출력한다.

5. 배열 변화 시각화

이해용 예시로 동전 [1, 2, 5], 목표 금액 10을 사용했다.

초기 상태

dp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

금액 0은 아무 동전도 쓰지 않는 한 가지 방법이 있으므로 dp[0] = 1이다.

동전 1원을 모두 반영한 뒤

dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

dp[money] += dp[money-coin] 은 “현재 동전을 하나 더 붙이는 방법 수”를 누적한다는 뜻이다.

동전 2원을 모두 반영한 뒤

dp = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

dp[money] += dp[money-coin] 은 “현재 동전을 하나 더 붙이는 방법 수”를 누적한다는 뜻이다.

동전 5원을 모두 반영한 뒤

dp = [1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

dp[money] += dp[money-coin] 은 “현재 동전을 하나 더 붙이는 방법 수”를 누적한다는 뜻이다.

6. 왜 이런 식으로 누적되는가

왜 동전이 바깥 루프일까?

동전별로 차례대로 누적해야 순서만 다른 경우(예: 1+2와 2+1)를 중복 계산하지 않는다.

최종 해석

예시에서 dp[10] 값이 10원을 만드는 조합의 개수다. 실제 문제도 같은 원리로 목표 금액까지 누적한다.

7. 자주 헷갈리는 포인트

• 이 문제는 조합의 개수 문제다. 최소 개수 문제와 점화식이 다르다.
• 금액 루프를 거꾸로 돌리면 0/1 방식처럼 되어 다른 문제가 된다.
• dp[0]=1 초기화를 빼먹으면 모든 값이 0으로 남는다.

8. 복잡도

테스트케이스 하나당 시간 복잡도는 O(NM) 이다.

1차원 DP 배열만 사용하므로 공간 복잡도는 O(M) 이다.

원문 문제 링크

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