[백준/G5/DP/자바] 2293. 동전 1

💡 문제

 

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다.

이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오.

각각의 동전은 몇 개라도 사용할 수 있다.

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

 

⌨ 입력

 

첫째줄 N / K ( 1 <= N <= 100 ) ( 1 <= K <= 1만 )

둘째줄 ~ N 줄  동전의 가치 10만 이하의 수

 

💻 출력 / 제한

 

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

 

---

 

풀이 방법

 

문제 유형 : 다이나믹 프로그래밍( DP ) 

 

문제 : 여러 동전으로 K 원 만드는 경우의 수 ( 단. 같은 동전 여러개 사용 가능 )

 

접근

동전이 몇개, 어떤 종류 동전이 사용 되는지 모른다.

동전이 최대 100개 이므로 탐색으론 불가능 하다 판단 하였고

이전의 결과 값을 사용하는 DP 문제 라고 생각 하였다.

 

누적 방법

떠오르지 않아 예시를 통해 찾았다.

ex)

3 4

1

2

3

 

경우의 수 ( dp[4] )

♣1 ( 1 * 4 )

♣2 ( 2 * 1 + 1 * 2 )

♣3 ( 2 * 2 )

♣4 ( 3 * 1 + 1 * 1 )

 

dp[ 4 ] = 4 가 되어야 한다.

어떻게 dp[ 4 ] = 4를 만들수 있을까?

 

Case 1, 2, 3 을 누적 해보자.

 

Case 1:

 

Case 2:

 

dp[ 2 ] = ♣( 1 * 2 ) + 추가 : ♣ ( 2 * 1 ) = 2

dp[ 4 ] = ♣ ( 1 * 4 ) + 추가 : ♣( 1 * 2 + 2 * 1 ) + ♣ ( 2 * 2 ) = 3

엇! 익숙한 수식이다.

 

♣( 1 * 2 ) + ♣ ( 2 * 1 ) 경우 2를 더 한 것과 같다.

dp[ 4 ] = dp[ 2 ] + dp[ 4 ]

dp[ i ] = dp[ i - num ] + dp[ i ]

 

Case 3:

 

dp 업데이트 : 자기 자신을 더 할 수 있는 dp[ 3 ] ~ 끝 이다.

 

dp[3] += 1 이 어떻게 되는 걸까?

 

dp[ 3 ] = ♣( 1 * 3 ) + ♣ ( 1 * 2 + 2 * 1 ) + 추가 : ♣( 3 * 1 ) = 3

수식 대로면 dp[ 0 ] + dp [ 3 ] 이다.

dp[ 0 ] = 1 ?

 

dp[ 0 ] 은 왜 1일까?

아무 동전도 쓰지 않는 경우의 수는 1가지 밖에 없구나!

 

---

전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Coin1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] dp = new int[K + 1];
        dp[0] = 1;

        for(int i = 1; i <= N; i++){
            int num = Integer.parseInt(br.readLine());
            if(num > K){
                continue;
            }
            for(int j = num; j <= K; j++){
                dp[j] += dp[j - num];
            }
        }
        System.out.println(dp[K]);
    }
}