백준 2293번 동전 1 (java)

[Gold V] 동전 1 - 2293

문제 링크

성능 요약

메모리: 14288 KB, 시간: 112 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 14일 19:03:02

문제 설명

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

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

입력

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

출력

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

풀이

예제 입력 1 복사

3 10
1
2
5

예제 출력 1 복사

10

 

이 예제를 기반으로 설명해보겠다.

 

맨 처음엔

 

1을 만들 땐 한 가지 방법이고

2를 만들 땐 1의 방법에 +1 하기, 자기 자신 더하기

3을 만들 땐 2의 방법에 +1하기, 1의 방법에 +2하기로 생각했다.

 

하지만 이렇게 만들면

 

1 = 1

2 = (1,1)   (2)

3 = (1,1,1) (2,1) (1,2)

 

로 2,1과 1,2 중복이 발생해버렸다.

 

이를 해결하기 위해 정말 많은 생각을 해보았다.

 

결론은 2를 더하는 게 아니라 111 에서 11을 2로 대체시키는 것이다.

 

이를 위해선 먼저 제일 작은 수로 만들 수 있는 모든 경우의 수를 만들고

 

그 위에 2를 추가해 만들 수 있는 경우의 수를 업데이트 시켜줘야 한다.

 

그 이후엔 5를 추가해 만들 수 있는 경우의 수를 업데이트 시켜주면 된다.

 

위와 같은 방법이 성립되려면

 

현재 수가 6이라는 가정하에

 

dp[6] += dp[6 - 1]

dp[6] += dp[6 - 2]

dp[6] += dp[6 - 5] 로 점화식을 만들어주면 된다.

 

몰론 위의 과정이 1중 포문에서 이뤄진다면 맨 처음 언급했던 순서의 문제가 발생하므로,

 

2중 포문에서 1로 만들 수 있는 모든 경우의 수를 다 구하고,

1로 만든 경우의 수 위에 2를 더하고

1과 2로 만든 경우의 수 위에 5를 더해 중복을 없애줘야 한다.

 

전체 코드

public class Main {
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int[] x = new int[N];
        int[] dp = new int[S+1];

        dp[0] = 1;

        for(int  i = 0 ;i<N;i++){
            x[i] = Integer.parseInt(br.readLine());
        }

        for(int  i = 0;i<N;i++){
            for(int j = 1;j<=S;j++){
                if(j - x[i] >= 0) {
                    dp[j] += dp[j - x[i]];
                }
            }
        }

        bw.write(dp[S] + "");
        bw.flush();
    }
}