백준 9084번 동전(C++)

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

9084번: 동전

문제를 풀 때 dfs bfs 백트레킹 완전탐색으로 많이 풀다보니 TLE가 많이 발생한다는 느낌이 들었다. 이번 아레나에서도 아마 출력은 다 맞았을탠데 시간초과가 나서 문제를 풀지 못했다. DP라는 것도 알고 있었는데 못풀다니 기분이 너무 안좋았다. 그래서 DP를 열심히 풀어보고 있다. 그런데 DP는 구글링 안하면 풀수가… ㅠㅠㅠ 언젠가 온전히 내 힘으로 풀기를 고대한다.

 

이 문제는 포함할지 안할지 결정가능하고 한번에 여러개를 넣을 수 있는 배낭문제이다. 넣는다 or 안넣는다라는 0-1 선택지가 아니기 때문에 0-1 배낭 문제는 아니다.

 

• DP[A] = B
  • 이 코드의 의미는 A를 만드는데 B가지 수가 있다는 의미이다!

먼저 1,2,3 원으로 4를 만드는 경우를 가정하여 점화식을 얻어보자.

1. 1원 만을 사용해서

DP[1] = 1 밖에 없으므로 1개 이다.

DP[2] = 1 +1 이므로 1개이다.

DP[3] = 1 + 1 + 1 이므로 1개이다. DP[4]까지 반복된다. 이것을 먼저 기억해둔다.

 

1. 2원까지 사용해서 만들어보자

DP[1] = 1 2원으로 만들 수 없다.

DP[2] = 1원으로 만들었던 1개 + 이제 2원을 사용하므로 2개이다.

DP[3] = 1원으로 만들었던 1개 + 1원에다가 2원까지 더할 수 있으므로 2개이다.

DP[4] = 1원으로 만들었던 1개 + 1 + 1 +2 , 2 + 2 이므로 4개이다.

 

여기서 중요한 건 2,3,4이다. 먼저 상기하고 가야할 것은 N까지 만들어져 있다고 가정할 때 DP[N]은 N 을 만들어낼 수 있는 경우의 수 이다. 그러므로, 만약 N + 2까지 수를 사용하여 경우의 수를 처음으로 발견한다고 하면 DP[N + 2] = DP[N + 2] + 1 이 된다.

 

이를 알아두고 DP[2]를 생각해본다.

 

1로 DP[2]를 만든적이 있으니. DP[2] = DP[2] + 새로운 경우의 수

여기서 새로운 경우의 수가 바로 위에서 상기했던 것이된다. 이제 2까지 사용하므로 2를 뺀 DP를 불러오는 것이다.

 

DP[2] = DP[2] - DP[0]

 

3,4 도 똑같은 맥락이다. 4를 생각해보면 지금까지 쌓아왔던 DP[4] + DP[4 - 이번코인수]

 

그러므로 DP[4] = DP[4] + DP[2] = 2 + 2 = 4가 되는 것이다.

반복문은 2중으로 돌아가는데, 여기서 바뀌는 것은 가장 작은 코인~ 원하는 액수 와, 코인들을 저장해놓은 인덱스가 필요하기 때문이다.

for (int j = 1; j <= N; j++) {
			for (int k = coin[j]; k <= M; k++) {
				DP[k] = DP[k] + DP[k - coin[j]];
	 }
}

i번째로 만들 수 있는 액수부터 계속 DP를 업데이트한다.

#include <iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int N, M;
		cin >> N;

		int DP[10001] = { 0, };
		int coin[21];

		for (int j = 1; j <= N; j++)
			cin >> coin[j];

		cin >> M;
		DP[0] = 1;
		for (int j = 1; j <= N; j++) {
			for (int k = coin[j]; k <= M; k++) {
				DP[k] = DP[k] + DP[k - coin[j]];
			}
		}

		cout << DP[M] << '\\n';
	}
}