동전 1 [자바]

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

2293번: 동전 1

 

동전 1 성공

 

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

0.5 초 (추가 시간 없음)

4 MB

63372

29829

22743

47.109%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3 10
1
2
5

예제 출력 1 복사

10

 

 

전형적인 DP문제입니다..

메모리제이션 지점을 찾는데 애를 먹었습니다.. 고수분들은 규칙을 쉽게 찾겠지만, 개인적으로 규칙이 안보인 문제..

 

예제를 기준으로 표를 만들어보겠습니다, K값이 입력되면 0부터 K원까지 경우의 수를 구하면 되는데, 단순하게 구하는 것이 아니라,

동전을 추가해가며 구해야합니다.

작은 동전만 썻을 경우부터 시작하여 크기가 작은 순으로 동전을 추가하며 경우의 수를 셉니다.

설명 생략하고 표부터 그려보면 아래와 같이 나오는데, 세로의 1,2,5 는 1원만 2원만 5원만 사용하겠다는 것이 아니라, 1원만 사용하는 것에서 2원까지 사용 1,2원사용경우에 5원까지 사용 이런 뜻입니다.

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4	4	6	7	8	10

 

이제 원리를 알아보자면.. 다음과같다습니다..

	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4	4	6	7	8	10

2원짜리동전과 1원짜리 동전으로 2원을 만드는 경우를 생각해보자면,  그 경우는 1원만으로 2원을 만드는 경우에다가  2원짜리와 1원짜리를 사용해서 0원을 만드는 경우에 2원짜리 하나를 더 쓴 경우일 것입니다. 

솔직히 이해안되니까 몇가지 경우 더 보겠습니다.

동전가치\금액	0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1	1
2	1	1	2	2	3	3	4	4	5	5	6
5	1	1	2	2	3	4	4	6	7	8	10

이번엔 2원짜리동전과 1원짜리 동전으로 5원을 만드는 경우를 생각해보자면, 그 경우는 1원만으로 5원을 만드는 경우에다가 2원짜리와 1원짜리를 사용해서 3원을 만드는 경우에 2원짜리 하나를 더 쓴 경우일 것입니다. 

 

대충 이런식이면 점화식을 잡을수있습니다.

N을 테이블의 행 K를 열 즉 금액으로 잡으면 

dp[N][K]=dp[N-1][K]+dp[N][K-{해당 행의 동전의 가치}]

dp로 설계할거니까 초기화가 중요합니다.

0원을 만드는 경우는 아무것도 사용하지않는 1가지로 초기화 할 것입니다.

 

아래는 이차원 dp로 설계한 코드입니다.. 일차원으로 다듬기가 가능하지만 우선은 이차원으로 설계한 코드를 작성해보았습니다.

package org.example;

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Q2293 {
    static int dp[][];
    static long count=0;

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        String[] list = str.split(" ");
        int N=Integer.parseInt(list[0]);
        int K=Integer.parseInt(list[1]);
        dp =new int[N][K+1];
        int[] coins =new int[N];
        for(int n=0; n<N; n++){
            coins[n]=scan.nextInt();
        }

        Arrays.sort(coins);


        for (int i = 0; i < N; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= K; i++) {
            if (i % coins[0] == 0) {dp[0][i] = 1;}
        }

        for (int i=1;i<N;i++){
            for(int j=0;j<=K;j++) {
                if(j<coins[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                }
            }
        }


        System.out.println(dp[N-1][K]);

    }

}