>>>>>>>>>>>>>   https://www.acmicpc.net/source/9685295 <<<


지금 다시 복습중이라서 예전에 푼 dp문제 하나하나 푸는 중임


예전에 이 동전문제 풀었을 땐 개허접이라 답 보고 1차원 배열 갖다가 냈는데


이번에는 2차원 배열 그려가면서 하나하나 채워넣으니까 더 이해도 잘되고 속도도 향상됨.


내가 만들어본 식임.


dp[i][j] 를 i번째 동전까지 사용하면서 j원을 만드는 경우의 수라고 정의


if (j==0) 이면 0을 만드는 경우의 수도 1로 침 (아무것도 안한다, 즉 공집합 개념)


if (j - coin[i] >= 0) 이면 dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]];


설명하자면 i번째 동전까지 사용해서 j원 만드는 경우의 수는


i-1번째까지 사용해서 j원을 만드는 경우의 수와 i번째 동전을 사용해서 j-coin[i]원을 만드는 경우의 수를 더한 거임.


예를 들면


동전이 순서대로 [1, 2, 5] 있다고 가정


dp[2][4] 는 두번째 동전까지 사용해서 4원을 만드는 거니까 dp[1][4]의 경우의 수는 무조건 포함이다. 이건 당연한 거니까 이해가지?


그러면 어떤 변수를 더해야 dp[2][4]가 완성될까? 


그 답이 dp[2][4-coin[i]] --> dp[2][2] --> 즉 2번째 동전까지 사용해서 2원을 만드는 경우의 수다.


dp[2][2]를 이루는 경우의 수들에다가 현재 coin[i]를 더하면 4원이 만들어지니깐!


결국 dp[2][4] = dp[1][4] + dp[2][2] 라는 뜻 (coin[2]가 2원이라서)







사실 여기는 다 고수들이라 이런 문제 콧방귀 뀌면서 풀었겠지만


나는 안 잊어먹으려고 한 번 적어봄...