BOJ 2294 (동전 2)

• 문제
  n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
  
  사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
  
  
• 입력
  첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
  
  
• 출력
  첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

#include<iostream>
#include<algorithm>
#define MAX 101
using namespace std;
int n, k;
int coin[MAX];
int dp[10001];
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

int main()
{
	fast_io();
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> coin[i];
	}
	for (int i = 1; i < 10001; i++)
	{
		dp[i] = 999999;
	}

	for (int i = 0; i < n; i++)
	{
		/* coin[i]부터 시작하는 이유 -> 아래 금액은 어차피 coin[i]로 count 불가능하기 때문 */
		for (int j = coin[i]; j <= k; j++)
		{
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
		}
	}
	// 3항 연산자로 길이 줄 일 수 있다
	if (dp[k] == 999999) cout << "-1";
	else cout << dp[k];
	return 0;
}

    문제에서 최소 갯수를 요구하여 DP 방식을 생각했다. 최솟 값을 구할때는 큰수로 메모제이션을 위한 DP 배열을 매우 큰 값으로 초기화 시키고 시작을 하는 방법이 있다는 것을 알 수 있었다.

각 coin의 금액마다 반복문을 돌리고
dp[0]=0와 dp[j-coin[i]]+1을 이용해서 동전의 가치에 해당하는 dp의 인덱스 값은 1로 바꿀 수 있었다.

시간복잡도 : O(N^2)