[백준/2293] 동전 1 - JAVA

📌 문제

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

🦧 문제 풀이 접근

2차원 배열 dp를 만들어서 한 동전씩 가능한 경우의 수를 체크한다.
가진 동전이 현재 체크하는 동전보다 크거나 같은 경우

dp[i][j] = dp[i][j-현재 체크하는 동전]+dp[i-1][j]

을 한다.

💻 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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] coinArr = new int[n];
        for(int i=0;i<n;i++) {
            coinArr[i] = Integer.parseInt(br.readLine());
        }
        int[][] dp = new int[n+1][k+1];
        dp[0][0]=1;
        for(int i=1;i<n+1;i++) {
            for(int j=0;j<k+1;j++) {
                if(j<coinArr[i-1])
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = dp[i][j-coinArr[i-1]]+dp[i-1][j];
            }
        }
        System.out.println(dp[n][k]);
    }
}

🥇 결과

🎓 느낀점

현재 동전 크기에 따른 변화를 잘 파악하면 풀 수 있다.