BOJ 2293 동전1

기본적인 dp문제들 중 하나이다.
하지만 어렵다...

2차원 dp 풀이 참고 : https://www.acmicpc.net/board/view/6217
2차원 dp로 푸는 방법이 가장 이해하기 쉽지만 이 문제에서는 메모리 제한이 4GB이기 때문에 2차원 dp를 쓸 경우, sliding window기법을 이용해야 한다.

혹은 2차원 dp의 식을 잘 살펴보고 표로 그려보면, 없어도 되는 부분이 있다. 그래서 그 식을 좀 수정하면 1차원 dp로 바꿀 수 있다. 

2차원 dp를 간단히 만든 1차원 dp랑 같긴하지만, 처음부터 1차원 dp로 생각해서 짠다고 해보자. 1차원 dp로 프는 방법이 좀 이해하기가 어려운데, 그리고 이해해도 시간이 지나면 다시 이해못하게 되는 그런... 그래서 여기서 내가 이해한 것을 기록해놓으려 한다.

d[k]=주어진 동전 n개를 적절히 사용해서 k원을 만들 수 있는 경우의 수.
d[k]=d[k-a[1]]+d[k-a[2]]+d[k-a[3]]+...+d[k-a[n]] (a[1]~a[n]은 n개의 동전들)
==>이렇게 k원을 만들 수 있는 경우를 사용할 수 있는 동전을 다 사용한 경우들의 합으로 할 경우, 중복이 발생한다. 1+2+1과 1+1+2 는 같은데, 다른 것으로 개수를 세는 것이다.

그렇다면 어떻게 해야할까?

바로 하나의 동전을 이용해서 모든 k에 대해 k를 만들 수 있는 경우의 수를 구하고, 이제 그 동전은 사용하지 않는다. 그리고 구해놓은 것을 이용해서 다음 동전을 이용해서 모든 k에 대해 k를 만들 수 있는 경우의 수를 모두 구한다... 이런식으로 동전을 하나씩 사용하면서, 동전 하나에 대해서 모든 k에 대한 경우의 수를 구하고, 그 동전은 더 이상 사용하지 않는식으로 하면 중복되지 않는 경우의 수를 구할 수 있다.

참고) 이해가 잘 안되면, 직접 써보는 것이 이해하기 수월하다.
추천 예제 : k=7, n=3, 동전 : 1원, 2원, 5원
0 : X
1 : 1*1
2 : 1*2
3 : 1*3
...