문제해석

N종류의 동전을 가지고 K값을 만들어낼때 최소 동전의 갯수를 구하면 된다.
예를들어 1,5,12 동전을 가지고 있고, K=15를 만들어 낼때 동전개수는
1원으로만 만들경우 최대 15개가 필요하고, 5원으로 만들경우 최소 3개, 12원+1원+1원+1원 으로 만들경우는 4개가 필요하다.

잘못된 접근(시간초과)

모든 동전을 한개한개 다 추가해가면서 K값보다 동전값의 합이 커지는경우를 제외하면서 탐색해봤다. 즉, DFS로 접근하면서 조건에 해당하지 않은경우 더이상 탐색을 진행하지 않게 탐색하였다
조건은
1. 지금까지 더한 동전갯수가 이전합에서 나온 동전갯수보다 많을경우 return
2. 지금까지 더한 동전 값의 합과 K값이 일치할경우 기존 저장된 정답값과 비교하여 더 작을경우 값 저장 (가장 작은 값을 구하는것이므로)

이 경우는 시간초과가 난다.

void coin(int sum,int count)
{
	if (count>=answer)
	{
		return;
	}

	if (sum==K) // 끝인경우
	{
		if (count<answer)
		{
			answer = count;
		}
	}
	else { 
		for (int i = 0; i < N; i++)
		{
			if (sum+coinList[i]<=K)
			{
				coin(sum+coinList[i], count+1);
			}
		}

	}
}

DP 해설

함수 하나를 만들어서 DP[X]=Y 를 정의해보자.
X는 동전값의 합이고, Y는 그 값을 만드는데 필요한 최소 동전개수이다.
위 정답같은경우 15를 만드는 최소동전의 개수가 3이므로 DP[15]= 3으로 나타낼수 있다.

값이 작은동전부터 케이스를 분류해보자.

케이스 1

1원으로 15원을 만드는 최소개수
DP[1]=1이고, DP[2] = DP[1]+1로 만들수 있으므로, DP[2] =2, 같은원리도 DP[3]=3,DP[4]=4... DP[15]=15이다.

케이스 2

5원으로 15원을 만드는 최소개수
DP[1]은 5원으로 만들수 없다. 2,3,4도 마찬가지, DP[5]=DP[0]+1이므로 DP[5]=1이다.
DP[6]=DP[1]+1이므로 DP[6]=2이다. DP[10]=DP[5]+1=2, DP[15]=DP[10]+1=3

케이스 3

12원으로 15원을 만드는 최소개수
DP[12]=DP[0]+1 = 1, DP[15]=DP[3]+1 = 4

즉 DP[15]=3임을 구할수 있다.

점화식

DP[j] = MIN(DP[j],DP[j-coin[i]]+1) 임을 알수 있다.

	int DP[10001] = { 0, };
	int n, k, coin[101];


	cin >> n >> k;

	for (int i = 1; i <= k; i++)
	{
		DP[i] = 10001; // 만들수 없는경우 10001로 표현
	}

	for (int i = 1; i <= n; i++) {
		cin >> coin[i];

		for (int j = coin[i]; j <= k; j++) {
			DP[j] = min(DP[j], DP[j - coin[i]] + 1);
		}
	}

	if (DP[k]==10001)
	{
		cout << -1 << endl;
	}
	else {
		cout << DP[k] << endl;
	}

참고
https://itguava.tistory.com/67
https://jaemin8852.tistory.com/163
https://yabmoons.tistory.com/535