[JAVA] 백준 동전1

동적프로그래밍(DP) 문제이다.

 

• dp[i] = dp[i] + dp[i - coin]이다.
  • 문제와 같은 입력이 주어졌을 때
    1. 1원 짜리 동전으로 1원 부터 10원까지 만들 수 있는 가짓수를 구한다.
    2. 2원 짜리 동전으로 2원 부터 10원까지 만들 수 있는 가짓수를 구한다. (1원으로 구한 값을 이용하여 구한다.)
    3. 5원 짜리 동전으로 5원 부터 10원까지 만들 수 있는 가짓수를 구한다. (2원으로 구한 값을 이용하여 구한다.)

 https://dragon-h.tistory.com/10

 

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

public class Main {
    static int n,k;
    static int[] coin;
    static int[] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n= Integer.parseInt(st.nextToken());
        k= Integer.parseInt(st.nextToken());
        coin= new int[n];
        memo = new int[k+1];
        for(int i =0; i<n; i++) coin[i] = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++){
            System.out.println("i:" + i);

            for (int j = coin[i]; j <= k; j++) {
                memo[j] += memo[j-coin[i]];
                System.out.println(coin[i]);
            }
        }
    }

}