<Algorithm> 67. 2293번 동전 1

2293번 동전 1

• DP 응용문제, DP를 다시 생각하게 만든 문제
• DP는 단순히 이전 결과 값을 저장해서 해당 결과 값을 유도하는 것이라고만 생각했었다. 그래서 인지 이걸 어떻게 식을 세워야 하는 지에 대해서 감을 잡을 수가 없었다.
• 이 문제는 적립형식으로 i번째 코인으로 만들 수 있는 경우의 수를 최대 합계까지 확인하고 다음 코인으로 넘어가서 반복한다.  

참고 & 출처 http://www.crocus.co.kr/821 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        int[] coin = new int[N];
        for(int i = 0; i < N ; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        
        int[]dp = new int[1<<16];
        dp[0] = 1;
        // 자기 자신의 경우는 한가지
        
        for(int i = 0; i < N; i++)
            for(int j = 1; j <= K; j++) {
                if(j-coin[i] >= 0) {
                    dp[j]+=dp[j-coin[i]];
                }
            }
        System.out.println(dp[K]);
    }
}