파이문

2293. 동전 1 본문

문제 풀이/BOJ

2293. 동전 1

민Z 2017. 11. 12. 21:01
728x90

2293. 동전 1

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



동전 경우의 수 구하는, 나름 유명한 문제다. 역시나 알고스팟에도 같은 문제가 있다. (https://algospot.com/judge/problem/read/COINS)


구하려는 값 크기를 갖는 배열 dp를 만드는 데, 이 때 사이즈를 값 + 1 해야, 예외 처리 따로 하지 않고 쉽게 할 수 있다.

이렇게 만들어진 dp 에 경우의 수를 갱신하는데, i는 i원을 의미한다.


예를 들어서 dp[3]은 3원을 만드는 방법인데, 3원을 만드는 방법은 1원을 만드는 방법과 2원을 만드는 방법 두개를 더 하면 된다.


유투브에 강의 몇 개가 있어서 하나 첨부해 본다. https://www.youtube.com/watch?v=jaNZ83Q3QGc

import java.util.Scanner;

public class Main {

    public int problem2293(int[] coins, int k) {
        int[] dp = new int[k + 1];
        dp[0] = 1;

        for (int i = 0; i < coins.length; ++i) {
            for (int j = coins[i]; j < k + 1; ++j) {
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }
        return dp[k];
    }

    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] coins = new int[n];
        for (int i = 0; i < n; ++i) {
            coins[i] = sc.nextInt();
        }

        System.out.println(main.problem2293(coins, k));
    }
}


'문제 풀이 > BOJ' 카테고리의 다른 글

11053. 가장 긴 증가하는 부분 수열  (0) 2017.11.12
2579. 계단 오르기  (0) 2017.11.12
1149. RGB 거리  (0) 2017.04.04
1463. 1로 만들기  (0) 2017.04.03
1003. 피보나치 함수  (0) 2017.04.03
Comments