백준 9084 동전

1c2·2023년 3월 4일

DP algorithm 골드5 백준

baekjoon

목록 보기

4/18

백준 9084 ← 클릭
dp를 활용한 문제이다.

변수 설정

coin[i]: i번째 동전의 값
dp[k]: k원을 만드는 경우의 수

아이디어

n원 짜리 동전을 사용하기 k원을 만들기 위해서 k-n원 +n원이 필요하다

for문을 돌며 모든 동전에 대해 dp배열을 갱신한다.

예시

동전의 개수 N을 3이라고 하고, 각각의 값을 2, 3, 5원 이라고 하자.
coin[0] = 2
coin[1] = 3
coin[2] = 5

목표 값 M을 10이라고 하자.
2원짜리 동전을 활용하여 dp배열을 만들면 다음과 같다.

coin	1	2	3	4	5	6	7	8	9	10
2원	0	1	0	1	0	1	0	1	0	1

2원 짜리로 2원을 만드는 경우의 수는 한가지다. 4원을 만드는 경우의 수 또한 한가지다. ··· .10원을 만드는 경우도 한가지다.

3원짜리 동전으로 dp배열을 갱신하면 다음과 같다.

coin	1	2	3	4	5	6	7	8	9	10
2원	0	1	0	1	0	1	0	1	0	1
3원	x	x	1	1	1	2	1	2	2	2

3원을 만드는 경우를 보자. 2원짜리 동전으로 3원을 만드는 방법이 없기에 기존에 0이였는데 한가지가 추가되어 1이 더해졌다.
6원을 만드는 경우를 보자. 기존에 2원짜리 3개로 6원을 만드는 경우 1가지에 3원+3원인 경우가 추가되어 2가지가 되었다.
9원을 만드는 경우를 보자. 2원짜리 동전으로 9원을 만드는 방법이 없기에 기존에 0이였는데 6원+3원인 경우가 추가되었다. 6원을 만드는 방법은 2가지이기 때문에 2가 추가되어 2가 되었다.

같은 방법으로 5원짜리 동전을 활용하여 dp배열을 갱신하면 다음과 같다.

coin	1	2	3	4	5	6	7	8	9	10
2원	0	1	0	1	0	1	0	1	0	1
3원	x	x	1	1	1	2	1	2	2	2
5원	x	x	x	x	2	2	2	3	3	4

코드

github

#include<iostream>
using namespace std;

int main() {
	int T, N, M;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int dp[10001] = { 0, };
		dp[0] = 1;
		cin >> N;
		int coin[20] = { 0, };
		for (int j = 0;j < N; j++) {
			cin >> coin[j];
		}
		cin >> M;
		for (int j = 0; j < N; j++) {
			for (int k = coin[j]; k <= M; k++) {
				dp[k] += dp[k - coin[j]];
			}
		}
		cout << dp[M]<<endl;
	}
	return 0;
}