[백준/2294] 동전 2 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 골드5
출처 : 백준 - 동전 2

🦧 문제 풀이 접근

2차원 dp배열을 만든다.
2중 for문을 이용해 동전의 종류가 1개인 경우부터 3개인 경우로 확장해간다.
각 경우에서 0원부터 k원까지 표현할 수 있는 경우 중 가장 적은 경우를 저장해간다.

dp[i][j] = dp[i-1][j] 과 dp[i][j-추가된 동전]+1 중 작은 값

💻 code

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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int dp[][] = new int[n+1][k+1];
        for(int i=0;i<=k;i++) {
            dp[0][i] = -1;
        }
        for(int i=1;i<=n;i++) {
            int num = Integer.parseInt(br.readLine());
            for(int j=1;j<=k;j++) {
                if(j<num)
                    dp[i][j] = dp[i-1][j];
                else if(dp[i-1][j]==-1 && dp[i][j-num]==-1)
                    dp[i][j] = -1;
                else if(dp[i-1][j]==-1)
                    dp[i][j] = dp[i][j-num]+1;
                else if(dp[i][j-num]==-1)
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-num]+1);
            }
        }
        System.out.println(dp[n][k]);
    }
}

🥇 결과

🎓 느낀점

불가능한 부분에 -1 값을 넣어야 하는데 이 부분을 잘 예외처리 해줘야 한다.