관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DP

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

막무가내막내 2020. 6. 19. 19:59
728x90

 

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

 

2293번: 동전 1

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

백준 단계별풀기 동적계획법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

알고리즘 문제풀이 연습. Contribute to mtjin/algorithm_practice development by creating an account on GitHub.

github.com

 

 

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

728x90
Comments