백준/2293번/동전 1/골드5

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

문제 설명

Site: Baekjoon
Number: 2293
Category: Dynamic Programming
Rank: Gold 5

중복 선택이 가능한 배낭 문제로 생각하고 해결하여야 한다.

DP문제가 늘 그렇듯 초깃값을 잘 정하고 점화식만 세운다면 해결할 수 있다.

초깃값은 가장 처음에 주어진 코인으로 만들 수 있는 수라면 1을 넣고 아니라면 0을 채우고, 코인들마다 주어진 K까지 값을 늘려가며 해당 코인이 포함된 경우 나올 수 있는 경우의 수의 합을 구한다.

[예제 표]

초깃값을 설정한 후 2293번 문제의 점화식은 3개의 케이스로 나뉜다.

1.현재 만들고자 하는 값 n이 코인의 값보다 작은 경우: 이 경우에는 코인이 포함된 경우의 수가 없으므로 이전 값을 가져온다.
ex) 4원을 만들 수 있는 경우의 수가 3개 이고 현재 코인의 값이 5일 때, 5를 들어간 경우의 수는 나올 수 없으므로 그대로 3이된다.

2.현재 만들고자 하는 값 n이 코인의 값과 똑같은 경우: 코인 하나만 포함되는 새로운 경우의 수가 생기므로 이전 값에 1을 더한다.
ex) 5원을 만들 수 있는 경우의 수가 3개이고 코인의 값이 5일 때, 5만 들어가는 경우의 수가 생기므로 값은 3+1해서 4가된다.

3.현재 만들고자 하는 값 n이 코인의 값보다 큰 경우: 이 경우 만들 수 있는 경우의 수는 기존에 존재하던 경우의 수의 값과 n에서 코인의 값만큼 뺀 값을 만들 수 있는 경우의 수를 더한 값이다.
ex) 1,2원으로 10원을 만들 수 있는 경우의 수 6, 5원을 더해 10원을 만들 수 있는 경우의 수 4를 더해서 10이된다.

2차원 배열로 해결한다면 메모리 초과가 발생하기 때문에 1차원 배열로 해결하여야한다.

//메모리 초과 코드
#include <iostream>

using namespace std;

int dp[100][10001];
int coins[100];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> coins[i];

	for(int i = 1; i < K+1; i++)
	{
		if (i % coins[0] == 0)
			dp[0][i] = 1;
	}

	for(int i = 1; i < N; i++)
	{
		for(int j = 1; j < K+1; j++)
		{
			if (coins[i] > j)
				dp[i][j] = dp[i - 1][j];
			else if (coins[i] == j)
				dp[i][j] = dp[i - 1][j] + 1;
			else
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
			}
		}
	}

	cout << dp[N-1][K];

	return 0;
}

#include <iostream>

using namespace std;

int dp[10001];
int coins[100];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> coins[i];

	for(int i = 1; i < K+1; i++)
	{
		if (i % coins[0] == 0)
			dp[i] = 1;
	}

	for(int i = 1; i < N; i++)
	{
		for(int j = 1; j < K+1; j++)
		{
			if (coins[i] > j)
				dp[j] = dp[j];
			else if (coins[i] == j)
				dp[j] = dp[j] + 1;
			else
			{
				dp[j] = dp[j] + dp[j - coins[i]];
			}
		}
	}

	cout << dp[K];

	return 0;
}