[자바] 백준 2293번 동전 1. 2021-08-06

매우어려웠다. 무슨소리인지 접근조차 못했다.
그나마 이해한 것은

5원을 만드는 경우의 수=
1,2원을 통해 5원을 만드는 수(dp[5]) + 5원을 통해 5원을 만드는 수(dp[0]=dp[5-0]. 
6원을 만드는 경우의 수=
1,2원을 통해 6원을 만드는 수(dp[6])  + 5원을 통해 6원을 만드는 경우의 수(dp[1]=dp[6-5]).
7원을 만드는 경우의 수=
1,2원을 통해 7원을 만드는 수(dp[7]) +5원으로 7원을 만드는 경우의 수(dp[2]=dp[7-5]).
이렇게 된다.

**

여차저차 해서 난 이해했다고 착각했던 거 같다. 위에 밑줄친 부분인 k값(만들려는 값)에서 coin의 값어치를 뺀 값을 만드는 경우의 수를 더해주는 것이 왜 어째서 해당 coin의 경우를 더해주는 것인지 이해가 잘 안되었지만,=> 이 말도 이해가 잘 안 될 수 있는데 5원의 경우의 수를 더해주는 것이 왜 k값에서 coin을 뺀 값을 더해주는 것인가? 기억하자 외길 수순이다. 만약 5원으로 2원을 만들수 있는 경우가 2라면, 5원으로 7원을 만들 수 있는 경우는 얼마일까? 가능한 조합은 2+5 하나뿐이므로, 똑같이 2이다.

그래서 저러면 1,2원으로 만들수 5원을 만들수 있는 경우의 수 + 5원으로 5원을 만들수 있는 경우의 수 가 되는 것이다.

**
이유는 표를 그려 보면 된다.

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2(1 +1)	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4(3+1)	5	6	7	8	10

처음엔 이해가 잘 안되겠지만 표의 행은 동전의 가치 n 을 나타내었고, 열은 각 동전의가치 n을 사용해서 K원을 만들수 있는 경우의 수를 나타내었다.
우선 동전의 가치 이하의 수 K를 그 해당 동전을 사용해서 만들긴 불가능하다.
예) 2원으로 1원을 만드는 경우, 5원으로 1,2,3,4원을 만드는 경우.
이 경우는 그 이전 동전의 가치들로 만들수 있는 경우의 수를 그대로 쓸수 밖에 없다. 예) 2원으로 0,1을 만드는 경우는 1가지로 1원으로 0,1을 만드는 경우와 동일하다. (표에 파란색으로 표시한 부분.)
그런데 만약 동전의 가치와 같거나 큰 값을 만들려면 해당 동전을 사용할수 있다.(표에 빨간색으로 표시한 부분부터 행의 끝까지). 여기서 규칙이 중요하다. 5원으로 예를 들어 본다면, 만약 5원을 통해 5라는 값을 만든다고 했을때, 기존 dp[5]값(1,2원으로 5(K값)원을 만드는 경우의수(3) )에서 5원을 통해 5원(K값)을 만들수 있는 경우의 수를 더하는 경우가 있다(여기서 dp[0]값인 이유는 0+5=5 이므로 외길수순이므로 경우의 수가 같다). 즉, 기존의 dp[5] 값인 3은 1원과 2원을 통해서 만들수 있는 경우의 수만 나타낸 것이고, 이젠 5원을 쓸수 있으므로, 5원으로 만들 수 있는 경우의 수를 더해준 것이다.

표에서 밑줄친 부분들. 즉 내말을 액면가 그대로 점화식을 새우면 dp[5]=dp[5] (1, 2원으로 5원을 만들수 있는 경우의 수)+dp[0] ( 5원으로 5원을 만들수 있는 경우의 수) 이다.


이 것을 for문을 통해 차례대로 더해주면 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        int[] arr = new int[n + 1];
        int[] dp = new int[k + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = s.nextInt();
        }
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = arr[i]; j <= k; j++) {
                dp[j] = dp[j] + dp[j - arr[i]];
            }
        }
        System.out.println(dp[k]);
    }
}

dp[i]=dp[i]+dp[i-코인의 값] 이런 점화식이 탄생한다는 것이다.


공부시간 1시간.
고민시간 1시간.

아무리 봐도 이해가 되지 않는다... 일단 다른 블로그보고 대충 끼워맞추긴 했는데.. 아직도 이해 안됨-> 이젠 이해된다.
그냥 그 전까지 n값이 K 값보다 크거나 같은 경우, 해당 기존 dp[n]값에서 이전에는 포함시키지 않았던 k에 대한 경우의 수를 더해주는 것이라고 생각하면 된다.

많은 도움을 준 블로그.백준 2293번: 동전 1 :: 알고리즘(Problem Solving) 공부 블로그 (tistory.com)

백준 2293번: 동전 1