[AC] 2294 동전2

출처 : https://www.acmicpc.net/problem/2294

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2294.cpp

동전문제...

대놓고 나  DP입니다. 하는 문제이다. 정말 자주나오는 패턴이며 DP의 기본이라 할 수 있다. 

이 기본틀을 가지고 이렇게 저렇게 참 많이 바꿔서 문제가 나온다. 결국 다 비슷한 문제이며, 키워드만 정확히 이해하면 쉽다.

푼지는 꾀 되었으나 복습차 풀어봤다.

결국은 그거다. 동전 하나를 놓고 그 동전으로 만들수있는 경우의 수를 다 만든다. 그 다음에는 다음 동전으로 똑같은 경우를 체크하면서 쭈욱 확인한다. 핵심은 바로 이문장인데

	for (int i = 0; i < n; i++)
		for (int j = coin[i]; j <= k; j++)
			cnt[j] = min(cnt[j], cnt[j - coin[i]] + 1);

이 문장을 살펴보면 cnt[j] 값을 계속 갱신하는데 j는 그냥 값 그 자체이며 cnt[j-con[i]] 는 3원을 구하려면 10원에서 7원을 빼면 된다. 뭐이런거랑 똑같은거다. 그런식으로 갱신을 해나간다. 물론 뒤에 +1을 하는건 현재 자기 자신을 추가하려는 것이기 때문이다.

알아두면 참 편리한 기본이다.