[백준/자바] #2294

java 문법에 익숙해지기 위해서 당분간은 java 언어로 코딩테스트를 풀어보려고 한다. 첫 시작은 간단한 DP 문제로 풀어보았다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main {
    static int INF = 100000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] numberCommand = br.readLine().split(" ");
        int N = Integer.parseInt(numberCommand[0]);
        int K = Integer.parseInt(numberCommand[1]);
        int[] coins = new int[N];
        int[] DP = new int[K+1];

        for(int i=0; i<N; i++) {
            coins[i] = Integer.parseInt(br.readLine().strip());
        }
        br.close();

        DP[0] = 0;
        for(int i=1; i<=K; i++) {
            DP[i] = INF;
        }

        for(int i=1; i<=K; i++) {
            for(int j=0; j<N; j++) {
                if (coins[j] == i) {
                    DP[i] = 1;
                } else if (coins[j] < i) {
                    if (DP[i-coins[j]] + 1 < DP[i]) {
                        DP[i] = DP[i-coins[j]] + 1;
                    }
                }
            }
        }

        if (DP[K] == INF) {
            bw.write(String.valueOf(-1));
        } else {
            bw.write(String.valueOf(DP[K]));
        }
        bw.newLine();
        bw.flush();
        bw.close();
    }
}