[백준] 9084 동전

문제보기

import java.util.*;
import java.io.*;

public class Main{
  static int[][] d; // m원을 idx번째 동전까지 사용해서 만드는 경우의 수
  static int[] c; // 동전 배열
  
  static int go(int idx, int m){
    if( m == 0 ){ // 목표 금액에 도달! -> 종료
      return 1;
    }
    // 목표 금액보다 오바되었거나 더이상 사용할 수 있는 동전이 없을 때
    if( m < 0 || idx < 0 ){ 
      return 0;
    }
    // 메모된 것이 있다면 꺼내 쓰자
    if(d[m][idx] != -1 ){
      return d[m][idx];
    }
		
    // 결과를 담을 변수
    int res = 0;
		
    // 여기가 핵심인데, 현재 만들어야하는 금액을 큰 동전 갯수를 최대한 써가면서
    // 하나씩 줄여가며 재귀를 보내주는 것이다
    // 이렇게 해야 중복되는걸 세지 않게 된다 
    for(int i = m/c[idx] ; i >= 0 ; i-- ){
      res += go(idx-1, m-c[idx]*i);
    }
		
    // 메모이제이션
    d[m][idx] = res;
    return res;

  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while( t-- > 0 ){
      int n = Integer.parseInt(br.readLine());
      c = new int[n];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i = 0 ; i < n ; i++){
        c[i] = Integer.parseInt(st.nextToken());
      }
      int m = Integer.parseInt(br.readLine());
      d = new int[m+1][n];
      for(int i = 0 ; i <= m ; i++ ){
        Arrays.fill(d[i], -1); // -1로 초기화
      }
      // 가장 큰 동전부터 사용하면서 m을 만들 수 있는 경우를 찾아본다 
      System.out.println(go(n-1, m));
    }

  }
}