[백준 알고리즘 풀이] 9084번 동전

동전문제는 보통 완전 탐색으로는 속도가 나오지 않기 때문에 동적 계획법을 사용해야하는데, 총액과 동전을 2d 행렬로 놓고, 점진적으로 100원을 만들수 있는 경우의 수를 증가하면서 얻어가는 점화식을 도출하는게 핵심이다. 아래는 iterative 방식인데 recursive와 memoization으로도 가능하다.

import java.util.Scanner;

/*
 * 9084번 동전
 */
public class Main {
  static int[] a;
  static int[] memo;
 
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int tests = sc.nextInt();
    while (tests > 0) {
      int n = sc.nextInt();
      int[] m = new int[n];
      for (int i = 0; i < n; i++)
        m[i] = sc.nextInt();
 
      int total = sc.nextInt();
      int[][] t = new int[n + 1][total + 1];
      for (int i = 0; i <= m.length; i++) {
        t[i][0] = 1;
      }
 
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= total; j++) {
          if (m[i - 1] > j) {
            t[i][j] = t[i - 1][j];
          } else {
            t[i][j] = t[i - 1][j] + t[i][j - m[i - 1]];
          }
        }
      }
 
      System.out.println(t[n][total]);
      tests--;
    }
    sc.close();
  }
}