[백준] 2293번 : 동전 1

문제

 

 

접근 방식

1원, 2원, 5원 총 3가지의 동전으로 1원부터 10원을 만드는 경우를 적어보면 다음과 같다.

1	1
2	11 2
3	111 12
4	1111 112 22
5	11111 1112 122 5
6	111111 11112 1122 15 222
7	1111111 111112 11122 115 1222 25
8	11111111 1111112 111122 1115 11222 125 2222
9	111111111 11111112 1111122 11115 111222 1125 12222 225
10	1111111111 111111112 11111122 111115 1111222 11125 112222 1225 22222 55

 

다시 1원만 사용한 경우, 1원과 2원을 사용한 경우, 세 가지 동전을 모두 사용한 경우로

경우의 수가 몇 개인지 정리해보면 다음과 같다. (0번 인덱스는 1이다.)

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

 

1원 동전으로는 값만큼 동전을 사용하면 모든 값을 만들 수 있기 때문에 모두 한 가지일 것이니 넘어가고

2원까지 추가로 사용해 n원을 만드는 경우를 먼저 생각해보겠다.

 

2원을 사용해서 2원 미만의 값은 당연히 만들 수 없으니

미만의 값들은 이전의 값을 그대로 사용하고 넘어가면 되고

2원 이상부터는 2원 동전을 사용할 수 있으니 값이 달라질 것이다.

 

위의 표에서 1원과 2원을 사용해 2원을 만드는 경우를 살펴보면

(1원으로 2를 만드는 경우인 1) + (2원으로 2 - 2원을 만드는 경우인 1) = 2가 되고

10원을 만드는 경우를 살펴보면

(1원으로 10원을 만드는 경우인 1 + 2원으로 (10 - 2)원을 만드는 경우인 5 = 6이 된다

 

이제 5원 동전까지 사용하는 경우도 마찬가지로

5원 이상부터 테이블의 값을 변경해주면 되고

10원을 만드는 경우를 살펴보면

(1원과 2원으로 10원을 만드는 경우인 6) + (5원으로 10 - 5원을 만드는 경우인 4) = 10이 된다.

 

점화식으로 정리하면 다음과 같다. (i는 목표가치, j는 현재 동전의 가치)

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

 

이때 dp[0] = 1로 초기화 해주어야

동전의 가치가 K인 경우를 처리할 수 있고

동전의 가치 이상의 dp 테이블을 수정할 때 처음에 dp[0]을 호출할 일이 있기 때문에

이를 0인 초기값으로 냅둬두면 테이블의 값이 변하지 않는다.

 

 

풀이

public class Main {

	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] = 0;

		for (int i = 0; i < n; i++) {
			int coin = Integer.parseInt(br.readLine());

			for (int j = coin; j <= k; j++) {
				dp[j] += dp[j - coin];
			}
		}

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