[백준] 2294번 - 동전 2 (동적 계획법)

글의 순서가 우연히 동전 1 다음이 됐지만 동전1을 풀고나서 다른 문제를 많이 풀었다.

이 문제를 풀다가 주의해야 할점을 발견해서 정리한다.

동적 계획법 문제에서 cache의 최소 값을 구해야 할 경우 처음에 cache배열을 큰 값으로 초기화하곤 했다.

 

int main()
{
	cin >> N >> K;
	for (int i = 1; i <= N; i++)
		cin >> coin[i];
	
	for (int i = 1; i <= K; i++)
		cache[i] = 100001;
    
    int answer = DP(K);
    if(answer==100001)
    	cout << -1;
    else 
    	cout << answer;
}

cache[i]는 동전들을 사용해서 i원을 만들 수 있는 최소 개수이다. 내가 이렇게 처음에 cache[i]를 100001로 초기화한 이유는 -1로 초기화하면 DP함수에서 min을 사용할 때 문제가 생기기 때문이다.

 

int DP(int x)
{
	if (x == 0)
		return 0;
	int& ret = cache[x];
	if (ret != 100001)
		return ret;

	for (int i = 1; i <= N; i++)
	{
		if (x >= coin[i])
		{
			ret = min(ret, 1 + DP(x-coin[i]));
		}
	}
	return ret;
}

min으로 기존 ret과 비교해 작은 것을 적용시키기 때문에 -1로 초기화 하면 ret은 무조건 -1이 된다.

그래서 100001로 처음에 초기화한 것인데... 이러면 중대한 문제가 발생한다.

만약 DP(x)가 동전들로 조합을 할 수 없어 그대로 ret = 100001로 반환됐다고 하자. 그러면 다음에 DP(x)를 계산할 때

if (ret != 100001) return ret; 이 조건에 부합하지 않기 때문에 또 다시 계산을 해야한다.

즉 메모이제이션이 적용되지 않는다!

 

int DP(int x)
{
	if (x == 0)
		return 0;
	int& ret = cache[x];
	if (ret != -1)
		return ret;

	ret = 100001;
	for (int i = 1; i <= N; i++)
	{
		if (x >= coin[i])
		{
			ret = min(ret, 1 + DP(x-coin[i]));
		}
	}
	return ret;
}

그래서 해결법은 처음에 기존 방법대로 memset으로 cache배열을 -1로 초기화하고

ret = -1이 아닌 경우에 ret=100001로 초기화한다. 그러면 -1과 구분되어 다음에 DP(x)를 계산할 때 바로 100001을 반환한다. 중요한 것은 계산이 안돼있는 경우(-1)와 계산이 됐지만 동전들로 조합을 할 수 없는 경우(100001)를 분리하는 것이다.