[백준] 동전 1 2293 - JAVA

문제

https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

풀이

DP 문제

 

DP[ i ] 는 i원이 만들어지는 경우의 수를 나타낸다. 

예를 들어 1원, 2원, 5원으로 2원을 만든다면 DP[2] 는 2가 될 것이다.

 

DP식은 다음과 같다.

DP[num] = DP[num] + DP[num - coin]

 

문제에 나와있는 예시가 입력으로 주어졌을때

1. DP에 1원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다.

2. DP에 1원과 2원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다.(이전에 구한것을 가지고 구한다.)

3. DP에 1원, 2원, 5원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다.(이전에 구한것을 가지고 구한다.)

 

1. 초기화 단계. DP에 1원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다.

(1원은 어떤 수와도 나누어 떨어지기 때문에 모든 수를 1원을 가지고 만들 수 있다. 만약, 2원을 가지고 만든다면 2,4,6,8,10만 만들수 있기 때문에 2,4,6,8,10의 DP값만 1이 될것이다.)

i	1	2	3	4	5	6	7	8	9	10
DP[i]	1	1	1	1	1	1	1	1	1	1

 

2. DP에 1원과 2원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다.(이전에 구한것을 가지고 구한다.)

i	1	2	3	4	5	6	7	8	9	10
DP[i]	1	2	2	3	3	4	4	5	5	6

이 경우에는 2부터 시작하면 된다. 왜냐하면 2로는 1을 못만들기 때문이다.

DP를 만들때 앞에서 부터 차례대로 만들게 된다. 앞에서부터 차례대로 만든것을 가지고 DP값을 구하면된다. 

예를 들어 2를 이용하여 5를 만든다고 해보자. 

이미 1+1+1+1+1 로 DP[5]에는 한가지가 들어있다. DP[3] 은 1+1+1과 1+2로 두가지가 나온다. 이때 이 각각에 2를 더해주면 5가 나오게 된다. 따라서 DP[5]는 기존의 DP[5]값과 DP[3] 값을 더해주면 되는 것이다.

 

3. DP에 1원, 2원, 5원으로 1원~10원까지 만들어질 수 있는 경우의 수를 넣는다.(이전에 구한것을 가지고 구한다.)

i	1	2	3	4	5	6	7	8	9	10
DP[i]	1	2	2	3	4	5	6	7	8	10

이 경우에는 5부터 시작하면 된다. 

이 경우도 2번에서 시행했던 것과 마찬가지다.

5로 7을 만들 차례라고 생각해보자. 이미 DP[7]에는 1+1+1+1+1+1+1, 1+1+1+1+1+2, 1+1+1+2+2,1+2+2 로 4가 저장되어있다. DP[2]에는 1+1, 2가 들어있다. 이 각각에 5를 더하면 7이 된다. 따라서 DP[7]의 값은 4+2 로 6이 된다.

 

따라서 점화식이 DP[num] = DP[num] + DP[num - coin] 이 되는 것이다.

 

이때 문제에서 메모리 크기 제한이 4MB이다. 따라서 일차원 배열을 이용해서 풀어야한다.

 

코드

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

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		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];
		int arr[] = new int[n+1];

		for(int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		// 초기화
		for(int  num = 1; num <= k; num++) {
			if(num % arr[1] == 0) {
				dp[num] = 1;
			} 		
		}
		
		for(int i = 2; i <= n; i++) {
			if(arr[i] <= k)
				dp[arr[i]] += 1;	
			for(int  num = arr[i] + 1; num <= k; num++) {
				if(arr[i] <= num)	{
					dp[num] = dp[num] + dp[num - arr[i]];
				}
			}
		}

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