[문제풀이] B2293 동전1

동전1

---

  🪅. dp에서 '메모이제이션'을 할 때, M[k]를 구하려면 M[1]부터 구해야한다. (1 <= k)
  🪅. dp는 재귀를 쓰거나, 반복문과 함께 써서 이전의 계산한 기록을 이용하는 알고리즘이다.
  🪅. 점화식에서는 어떤 규칙을 찾느냐가 중요한게 아닌, 이전의 기록을 어떻게 이용하느냐가 중요하다. 
       => 지금 구하려는 값이 이전의 기록과 비교해서 어떤 점이 달라졌는지에 초점을 맞춘다.

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;

  public class B2293_동전1 {
      static int n;
      static int k;
      static int[] coins;
      static int cnt;
      static int[] M;
      public static int dp(int r, int coin) {
          if(r == coin) {//1, 2, 5
              return M[r] = M[r] + 1;
          }
          if(r >= coin) {
              return M[r] = M[r] + M[r-coin];
          }
          return M[r] = M[r];
      }
      public static void init() throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer token = new StringTokenizer(br.readLine(), " ");
          n = Integer.parseInt(token.nextToken());
          k = Integer.parseInt(token.nextToken());
          coins = new int[n];
          M = new int[k+1];

          for(int i = 0; i < n; i++) {
              coins[i] = Integer.parseInt(br.readLine());
          }
      }
      public static void main(String[] args) throws IOException {
          init();
          for(int i = 0; i < n; i++) {
              int coin = coins[i];
              for(int j = 1; j <= k; j++) {
                  dp(j, coin);
              }
          }
          System.out.println(M[k]);
      }
  }

💡.문제 접근 과정
: 예제 입력처럼 결국 M[10](메모이제이션)을 구하려면 M[1]부터 구해야 한다.
경우의 수를 구할 때는 확실한 기준을 가지고 기준별로 차근차근 구해나간다.

1 1 1 1 1 1 1 1 1 1      [1] (COIN 1 or 2 or 5만쓸 때 경우의 수)
1 2 2 3 3 4 4 5 5 6    [2] (COIN 1 or 2 만쓸 때 경우의 수)
1 2 2 3 4 5 6 7 8 10   [3] (COIN 1 or 2 or 5만쓸 때 경우의수)

변화가 처음 생기는 부분을 기록해 둔다.
(처음 배열 M은 초기값이 모두 0이다.)
[1]
M[1] = M[1] + 1


[2]
M[2] = M[2] + 1
M[4] = M[4] + 2 (M[2])
M[6] = M[6] + 3 (M[4])
M[8] = M[7] + 4 (M[5])
M[10] = M[10] + 5 (M[8])

ex. M[4] = M[4] + M[2]인 이유
   [1]의 경우의 수 1 1 1 1 => 1개
   [2]의 경우의 수 1(기존 M[4]값) + 2 1 1, 2 2
   => 2를 최소 1개 쓴다고 가정했을 때 (4-2) 나머지 2를 만들 수 있는 경우의 수 +2


[3]
M[5] = M[5] + 1
M[7] = M[7] + 2 (M[2])
M[8] = M[8] + 3 (M[3])
M[10] = M[10] + 4 (M[5])

규칙이 보이는 부분은 if문으로 따로 빼서 점화식을 써주고,
나머지 규칙이 보이지 않는 부분은
이전의 기록과 비교해서 어떤 부분이 변화되었고, 이전의 기록을 어떻게 이용할 지에 대해서 고민해야 한다.
결국, 특정 조건에서 M[r] = M[r] + M[r-coins[i]]라는 점화식을 얻을 수 있다.