동전1(다이나믹 프로그래밍)

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

2293번: 동전 1

 

단순 2차원 다이나믹 프로그래밍 문제라고 생각할 수 있지만 메모리 제한이 4MB다.

2차원 다이나믹 프로그래밍을 사용하면 int형 2차원 배열만 해도 거의 4MB에 근접하므로

메모리 제한을 해결하기 위해선 1차원 배열을 사용한 다이나믹 프로그래밍 기법을 사용하여야 한다.

 

일단 2차원 배열을 사용하여 다이나믹 프로그래밍이 어떻게 돌아가는지 생각해보자.

 

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

문제의 예제인 1, 2, 5원짜리 동전을 사용하여 10원을 만드는 경우의 수를 나타내는 2차원 행렬이다.

 

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

첫 행은 디폴트로 채워준다.

 

동전을 아예 쓰지 않고 0원을 만드는 방법은 1가지이므로 1을 채워주고

나머지 값은 0으로 채워준다.

 

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

설명을 위해서 두번째 행까진 채워주겠다.

 

두번째 행을 채우는 방법도 후술할 방법 그대로 따라하면 된다.

 

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

현재 코인보다 만들어야하는 숫자가 작으면 위의 값을 그대로 가져와준다.

 

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

현재 코인보다 만들어야하는 숫자가 같거나 크면 본격적으로 점화식이 시작된다.

 

1과 2로 2를 만드는 방법은 2가지가 존재한다 = (1, 1), (2)

(1, 1) 방법은 1로 2를 만드는 방법에서 2를 0개 추가한 것이다.

(2) 방법은 1로 0을 만드는 방법에서 2를 1개 추가한 것이다.

 

따라서 1로 2를 만드는 경우의 수와 1로 0(2-2*1)을 만드는 경우의 수를 합해주면 된다.

 

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

1과 2로 4를 만드는 방법을 보자 = (1, 1, 1, 1), (1, 1, 2), (2, 2)

(1, 1, 1, 1) 방법은 1로 4를 만드는 방법에서 2를 0개 추가한 것이다.

(1, 1, 2) 방법은 1로 2를 만드는 방법에서 2를 1개 추가한 것이다.

(2, 2) 방법은 1로 0을 만드는 방법에서 2를 2개 추가한 것이다.

 

따라서 1로 4를 만드는 경우, 1로 2(4-2*1)를 만드는 경우, 1로 0(4-2*2)을 만드는 경우의 수를 합해주면 된다.

 

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

다음과 같은 점화식으로 2차원 배열을 채워나가면 다음과 같은 값을 얻을 수 있다.

 

하지만 앞서 말했듯이 이 문제는 메모리 제한이 있어서 2차원 배열의 다이나믹 프로그래밍을 1차원 배열로 압축해야한다.

2차원 배열에서 우리가 사용했던 점화식을 정리해보면

DP[i][j] = DP[i-1][j] + DP[i-1][j-coin] + DP[i-1][j-coin*2] + DP[i-1][j-coin*3] + ... + DP[i-1][j-coin*n] ( j-coin*n >= 0, coin은 동전의 가치)

 

다음과 같은 점화식이 나온다.

여기서 j를 j-coin으로 치환해보면

DP[i][j-coin] = DP[i-1][j-coin] + DP[i-1][j-coin*2] + DP[i-1][j-coin*3] + DP[i-1][j-coin*4] + ... + DP[i-1][j-coin*n] ( j-coin*n >= 0, coin은 동전의 가치)

즉, 해당 점화식은 이렇게 압축할 수 있다.

DP[i][j] = DP[i-1][j] + DP[i][j-coin]

 

여기서 일차원 배열 상에서 i는 기존에 있던 값, i-1은 현재 단계에서 새로 쓰여진 값이라고 생각하고 점화식을 구성하면

DP[j] = DP[j] + DP[j-coin]

최종 경우의 수 = 현재 코인을 사용하지 않는 경우의 수 + 현재 코인을 하나 추가하는 경우의 수

이러한 점화식을 도출해낼 수 있다.

 

#include <iostream>
using namespace std;

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num, dest;
	cin >> num >> dest;

	for (int i = 1; i <= num; i++)
	{
		cin >> coin[i];
	}

	DP[0] = 1;

	for (int i = 1; i <= num; i++)
	{
		int curcoin = coin[i];
		for (int j = 1; j <= dest; j++)
		{
			if (curcoin <= j)
			{
				DP[j] = DP[j] + DP[j - curcoin];
			}
		}
	}

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