[BOJ S1][#DP]2293번 동전 1

동전 1 성공

 

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

0.5 초 (추가 시간 없음)

4 MB

66667

31574

24094

47.385%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3 10
1
2
5

예제 출력 1 복사

10

 

📝 풀이

DP를 연습하기 좋은 문제이다!

1, 3, 5로  예시들어보자 

	1	2	3	4	5	6	7
1	1	1	1	1	1	1	1
3	1	1	1+1	1+1	1+1	1+2	1+2
5	1	1	2	2	1+2	1+3	1+3

 

해당 같은 경우의 수가 나오는데 이것은

규칙적으로 보면

• 6이 나오는 경우의 수
  • 1의 경우 =  1
  • 3의 경우는 3이 나오는 경우의 수 = 2
  • 5의 경우 1이 나오는 경우의 수= 1
• 7이 나오는 경우의 수
  • 1의 경우 = 1
  • 3의 경우 4이 나오는 경우의 수 = 2
  • 5의 경우 2가 나오는 경우의 수 = 1
• 8의 경우 
  • 1의 경우 = 1
  • 3의 경우 5가 나오는 경우의 수 = 3
  • 5의 경우 3이 나오는 경우의 수 = 2

이것처럼 각 경우의 수를 구할 때 dp[k] += dp[k-n]를 반복하게 된다.

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

public class S1_2293{
    static int coin[];
    static int N, K;
    static int dp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        coin = new int[N];
        for(int i = 0; i < N; i++){
            coin[i] = Integer.parseInt(br.readLine());
        }
        
        dp = new int[K+1];
        dp[0] = 1;
        for (int i = 0; i < N; i++) {
		for (int j = 1; j <= K; j++) {
			if (coin[i] <= j) {
				dp[j] += dp[j-coin[i]];
			}
		}
	}
	System.out.println(dp[K]);
    }
}