[BOJ] 2293 | 동전 1

문제

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

풀이

DP를 사용하여 풀 수 있는 간단한 문제.

DP[i] = 가격이 i일때 만들 수 있는 모든 경우의 수

DP[i] += DP[ i - coin[j] ], (j = 0~n-1)

따라서 전체 시간복잡도는 O(nk)가 된다.

DP의 점화식을 2차원으로 세우면 메모리 초과가 나므로, 위와같은 1차원으로 짜주어야 한다.

for문을 돌 때, 가격이 i일때 경우의수를 0~n-1까지 도는 것이 아니라,

물건 번호가 j일때 가격을 1~k까지 DP를 업데이트 하는것에 주의하자.

소스

#include<iostream>
#include<algorithm>
using namespace std;

int n, k, dp[10010], coin[101];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i <n; i++)
		cin >> coin[i];
	dp[0] = 1;
	sort(coin, coin + n);
	for (int j = 0; j < n; j++) 
		for (int i = 1; i <= k; i++) 
			if (i >= coin[j])
				dp[i] += dp[i - coin[j]];
	cout << dp[k];
}