[C++] 백준 2298번 동전 1

 

1) 문제설명

백준 Online Judge 2293번 동전 1

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

2293번: 동전 1

 

2) 아이디어

DP문제는 항상 기준을 정해두고 생각해야 한다. 이번 문제 같은 경우 DP [X원이 될 수 있는] = 경우의 수로 놓고 생각하였다.

순차적으로 생각해보면 DP [1] : 1원이 될수있는 경우의 수는 1원짜리 하나로 만들수있기때문에 DP[1] = 1이 된다.

DP [2] : 2원이 될수있는 경우의 수는 1원짜리 2개 | 2원짜리 1개로 만들 수 있다. DP[2] = 2

DP[2] = 1원짜리 3개 | 2원짜리 1개 1원짜리 1개 | 3원짜리 1개로 만들 수 있다. DP [3] = 3

다시 세부적으로 정리해보면

DP [3]을 3원 짜리로 만든다면 DP[3] = DP[3] + DP[0] 이다. => 0원을 만드는 경우의수 + 3원 이기 때문

DP [3]을 2원 짜리로 만든다면 DP[3] = DP[3] + DP[1] 이다. => 1원을 만드는 경우의수 + 2원 이기 때문

DP [3]을 1원 짜리로 만든다면 DP[3] = DP[3]  + DP [2]이다. => 2원을 만드는 경우의 수 + 1원 이기 때문

즉 X원을 만드는 경우의 수는 D [X] = D[X] + D[X - Y원 짜리로 만들기]이다

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int dp[100001];

int main() {
	int n, k;
	int arr[1001];
	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++) { // 1 
			
			dp[j] = dp[j] + dp[j - arr[i]];
			
			
		}
	}
	cout << dp[k] << endl;
}