[백준] 2293번 - 동전 1 (동적 계획법)

DP문제는 너무 어렵다.

이 문제를 처음 보고 knapsack 알고리즘을 사용하면 되겠다고 생각해서 cache를 2차원 배열로 만들었다.

어찌어찌하여 예제가 테스트 성공하긴 했지만 int형으로 [100][10000] 크기의 2차원 배열을 만드니

메모리제한인 4MB를 넘어서 실패했다. 1차원 배열만으로도 문제를 풀 수 있었다.

 

	for (int limit = 1; limit <= K; limit++)
	{
		for (int row = 1; row <= N; row++)
		{
			if (limit % V[row] == 0 && cache[row - 1][limit] == 0)
			{
				cache[row][limit] = 1;
				continue;
			}
			cache[row][limit] = cache[row - 1][limit];

			for (int i = 1; V[row] * i <= limit; i++)
			{
				if (V[row] * i == limit)
					cache[row][limit]++;
				else
					cache[row][limit] += cache[row - 1][limit - V[row] * i];
			}
		}
	}
	cout << cache[N][K];

2차원 배열로 몸을 비틀며 푼 흔적이다. cache[N][K]에서 N은 V[1]부터 V[N]까지 요소를 사용가능함을 의미하고

K는 그 요소들을 합친 결과 값으로 직전에 knapsack 문제를 풀어서 그런지 배열을 똑같이 만들었다.

 

cache[0] = 1;
for (int i = 1; i <= N; i++)
{
    for (int j = V[i]; j <= K; j++)
    {
        cache[j] += cache[j - V[i]];
    }
}

하지만 1차원 배열로 풀어야했는데 그러기 위해서 cache[N]이 동전들로 N원을 만드는 가짓수로 저장해야 한다.

그리고 첫번째 동전부터 루프를 돌린다. 예제에서는 1원,2원,5원이 있고 이것들로 10원을 만드는 가짓수를 구하는데,

i=x인 루프에서 V[x]원이 무조건 하나 들어가는 경우를 더한다.

i=1일 때 

DP[1]+=DP[0];

DP[2]+=DP[1];

DP[3]+=DP[2];

이런 식으로 더해진다. 

1원이 무조건 들어가는 경우이므로 1원만 빼준 경우의 수를 더해주면 된다.

여기서 더해주는 DP[0],DP[1],DP[2]는 V[1]원을 사용했을 때 0원,1원,2원을 만들어내는 경우의 수이다.

i=2일 때

DP[2] += DP[0];
DP[3] += DP[1];
DP[4] += DP[2];

2원이 무조건 들어가는 경우이므로 2원을 빼준 경우의 수를 더해준다.

여기서 더해주는 DP[0],DP[1],DP[2]는 V[1]원과 V[2]원을 사용했을 때 0원,1원,2원을 만들어내는 경우의 수이다.

i=3일 때

DP[3] += DP[0];

DP[4] += DP[1];

DP[5] += DP[2];

여기서 더해주는 DP[0],DP[1],DP[2]는 V[1]원,V[2]원,V[3원]을 사용했을 때 0원,1원,2원을 만들어내는 경우의 수이다.

 

이중 루프를 사용해 i=N까지 루프를 돌면 DP[K]가 V[1]원~V[N]원까지 사용하고 K값을 만드는 경우의 수가 된다.

DP[0]=1로 초기에 설정해야 하는데 DP[2]+=DP[0]처럼 자기자신 하나만 들어가는 것도 경우의 수이므로  

DP[0]=1을 해줘야 체크된다.