[Java] 백준 2293 : 동전

문제 링크

1.

1시간 고민하고 점화식을 세우지 못해 해설을 참고했다.

dp문제는 정말 너무 어려운 것 같다.. 해설 이해하는 것도 시간이 꽤 걸렸다.

 

 

2.

두 가지 배열을 선언 한다.

coin배열은 사용할 수 있는 동전의 종류이고,

dp배열은 동전을 사용해서 합이 index원이 되도록 하는 경우의 수를 나타낸다.

 

가장 작은 동전을 사용했을 때 각 dp배열의 각 index원을 만드는 경우의 수를 계산하고, 그 다음 동전을 사용했을 때 경우의 수를 여기에 누적하는 방식으로 진행을 한다.

 

예를 들어,

1을 사용해서 2를 만드는 경우의 수는 1+1로 총 1가지 이다.

2를 사용해서 2를 만드는 경우의 수는 2로 총 1가지 이다.

 

1을 사용해서 3을 만드는 경우의 수는 1+1+1로 총 1가지 이다.

2를 사용해서 3를 만드는 경우의 수는 1+2로 총 1가지 이다.

 

1을 사용해서 4를 만드는 경우의 수는 1+1+1+1로 총 1가지 이다.

2를 사용해서 4를 만드는 경우의 수는 1+1+2, 2+2로 총 2가지 이다.

 

1을 사용해서 5를 만드는 경우의 수는 1+1+1+1+1로 총 1가지 이다.

2를 사용해서 5를 만드는 경우의 수는 1+1+1+2, 1+2+2로 총 2가지 이다.

5를 사용해서 5를 만드는 경우의 수는 5로 총 1가지 이다.

 

뭔가 규칙이 보이는가? 나는 이 규칙이 못찾아 헤멨다.

 

 

2를 사용해서 5를 만드는 경우의 수를 생각해 보면,

1과 2를 사용해서 3을 만드는 총 경우의 수이다.

 

즉, A를 사용해서 N를 만드는 경우의 수는 N-A를 만드는 총 경우의 수와 같다.

 

dp[j] = dp[j] + dp[j - coin[i]];

 

 

주의할 점은 중복을 방지하기 위해 사용하는 동전의 크기부터 구해야한다.

문제의 예시처럼 1, 2, 5를 사용해서 10을 만들려고 하면, 다음과 같이 dp배열이 형성된다.

 

1.

1을 사용했을 때

2.

1, 2를 사용했을 때

3.

1, 2, 5를 사용했을 때

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

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

        int[] dp = new int[k + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = coin[i]; j <= k; j++) {
                dp[j] = dp[j] + dp[j - coin[i]];
            }
        }

        System.out.println(dp[k]);
        sc.close();
    }
}

 

 

4.

none

 

[참고] https://dragon-h.tistory.com/10