BOJ 2293. 동전 1

🙇‍♀️[Gold V] 동전 1 - 2293

문제 링크

성능 요약

메모리: 2100 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 1월 12일 13:19:41

문제 설명

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2³¹보다 작다.

🚀풀이

dp문제였다.

냅색 알고리즘을 응용한 문제로 점화식이 중요했다.

점화식은 다음과 같다.
dp[j] += dp[j - arr[i]];
점화식의 의미는 j원을 만들 수 있는 경우의 수 이다.

예를 들어 아래와 같은 예제라면

3 10
1
2
5

결과는 10이여야한다.

int n, k;
int dp[20000];
vector<int> arr;
void solve()
{
	cin >> n >> k;
	arr = vector<int>(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end());

	dp[0] = 1;

	for (int i = 0; i < n; ++i)
	{
		for (int j = arr[i]; j <= k; ++j)
		{
			dp[j] += dp[j - arr[i]]; // 점화식
			cout << "j : " << j << " dp[" << j << "] : " << dp[j] << endl; // 중간 결과를 보기 위한 코드
		}
	}

	cout << dp[k];
}

위와 같이 작성하고 돌리면 아래와 같은 결과가 나온다.

냅색 알고리즘이 제대로 이해됐다면 쉽게 알거같은데 난 조금 어려웠다..

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k;
int dp[20000];
vector<int> arr;
void solve()
{
	cin >> n >> k;
	arr = vector<int>(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}

	sort(arr.begin(), arr.end());

	dp[0] = 1;

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

	cout << dp[k];
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}