동전 1

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

4 MB

46326

21078

15889

45.651%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

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

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

예제 입력 1 복사

예제 출력 1 복사

본인 해결 코드

package Baekjoon.dp;

import java.util.Scanner;

public class B2293 {
    public static void main(String[] args) {
        //인풋 생성
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }
        //~ 인풋 생성

        //솔루션

        /** 중심 개념 **/
        /** 1,2, 코인으로 3원을 만드는 경우의 수란?
         *  1원으로 만들 수 있는 경우는 1,1,1 뿐이므로 1개이다.
         *  그러므로 dp[3] 을 1원으로 구했을땐 1이다.
         *  2원으로 만들 수 있는 경우의 수는?
         *  2원을 포함하는 경우의 수이므로, 3원에서 2원을 뺀 1원을 만드는 경우의 수가 곧 2원으로 3원을 만들 수 있는 경우의 수이다.
         *  그러므로 dp[3] = 현재까지의 dp[3](현재까지의 3원의 경우의 수) + dp[1](현재까지 1원의 경우의 수)
         * **/

        //동전으로 만들 수 있는 경우의 수가 궁금한 금액만큼 + 1 크기의 배열을 생성
        int[] dp = new int[k+1];

        //다른 값의 기초값이 되는 0을 미리 1로 저장
        //1원의 경우의 수를 구하고,
        //동전의 종류가 1,2,4 인 경우에
        //1원 동전으로 1원의 경우의 수를 구할 경우
        //즉, 찾으려는 금액과 동전의 금액이 같은 경우에는 dp[0]이 나온다.
        //이런 기초값의 경우는 기본으로 1을 넣어준다.
        dp[0] = 1;

        //코인 갯수만큼 반복
        for (int i = 0; i < coins.length; i++) {

            //현재 코인으로 현재 금액을 만들 수 있는 경우의 수를 구하기 위한 반복
            //1원부터 ~ 경우의 수가 궁금한 목표 금액까지 반복, 0원은 기초값이기에 의미가 없어서 제외
            for (int j = 1; j < dp.length; j++) {

                //만약 1원의 경우의 수를 구하려는 동전의 종류가 3,4,5 일 경우
                //그리고 3원으로 만들 수 있는 경우의 수를 찾을 차례인 경우에
                //1원 - 3원 은 -2 이므로 dp[-2] 는 존재 할 수가 없다.
                //그래서 그런 경우에는 그냥 패스
                if((j - coins[i]) < 0)
                    continue;

                //중심 개념이다.
                dp[j] += dp[j - coins[i]];
            }
        }
        System.out.println(dp[k]);
        //~솔루션
    }
}

참고하자 (점화식이란)

https://www.youtube.com/watch?v=c5NA9gn6tJ0