[백준 DP] 2293번 - 동전 1

2293번 - 동전 1

 

<문제>

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

2293번: 동전 1

 

<문제풀이>

Ex) n = 3, k = 10

• arr 배열

i	1	2	3
arr[i]	1	2	5

• dp 배열 (dp[0] = 1, j)

1. 초기상태

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

 

2. i = 1일 때

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

arr[1] = 1이므로 index 1~10까지는 1로 만들 수 있는 숫자에 해당한다. 때문에 dp[1]~dp[10]까지 경우의 수 1을 더해준다.

 

3. i = 2일 때

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

arr[2] = 2이므로 index 2~10까지 2로 만들 수 있는 경우의 수를 더해준다. 

 

4. i = 3일 때

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

arr[3] = 5이므로 index 5~10까지 5로 만들 수 있는 경우의 수를 더해준다. 

이제 점화식을 찾을 차례다.

점화식을 도출하기 위해 규칙을 찾는 과정은 arr[2]에서 j = 3일 때부터 시작된다고 생각한다. 

dp[3]은 dp[3]에 dp[1]이 더해진 값이 저장된다. dp[4]에는 dp[4]에 dp[2]가 더해진 값이 저장된다. 

dp[10]에는 dp[10]에 dp[8]이 더해진 값이 저장된다. 

다음으로 arr[3]일 때, dp[5]은 dp[5]에 dp[0]이 더해진 값이 저장된다. dp[10]에는 dp[10]에 dp[5]가 더해진 값이 저장된다. 

즉,  점화식은 dp[j] = dp[j] + dp[j - arr[i]]이 된다.

 

<코드>

#include <iostream>
using namespace std;

int arr[101] = { 0, };
int dp[10001] = { 0, };

int main() {
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	dp[0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = arr[i]; j <= k; j++) {
			dp[j] += dp[j - arr[i]];
		}
	}

	cout << dp[k] << endl;
	
	return 0;
}

 

<결과>

 

 

2022.01.04