[알고리즘] 백준 2293 동전1 -dp-

 

https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

백준 단계별풀기 동적계획법2 의 동전1 문제입니다.

 

동전 1원, 2원, 5원의 모든 경우의 수를 dp에 축적해줍니다. 바텀업방식 

 

주석에 풀이를 써놨습니다.

[Java]

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] coin = new int[n];
        int[] dp = new int[k + 1]; // dp[해당가격] = 의 가치를 만들 수 있는 경우의 수
        for (int i = 0; i < n; i++) {
            coin[i] = sc.nextInt();
        }
        dp[0] = 1;
        for (int i = 0; i < n; i++) { //코인 종류별로 차례대로 불러옴
            int currentCoin = coin[i];
            for (int j = currentCoin; j <= k; j++) { //현재코인가격(currentCoin) ~ K 까지 dp 축적해나감
                dp[j] += dp[j -currentCoin]; // currentCoin 이 2라면  dp[2] 일때 dp[0] 축적, dp[3] 일때 dp[1], dp[4]일때 dp[2] 축적 ...(해당 동전의 모든 경우의 수 축적)
            }
        }
        System.out.println(dp[k]);
    }
}

https://github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%202293%20%EB%8F%99%EC%A0%841%20-dp-

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!!