[ boj : 22115 ] 창영이와 커피

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

22115번: 창영이와 커피

해설 : 하....일반적인 냅색 문제라고 하기엔 좀 뭔가 이상해서 많이 해맸습니다...,,

 

보통 최대값을 찾아 내라고 하는데 이 문제는 최소값을 찾아내라고 하더라구요 ㅠㅠㅠ

 

물론 최적화하여 풀면 간단하게 풀리지만, 생각이 안나서 2차원으로 풀려고 하다보니 많이 꼬였습니다.

 

먼저 점화식을 선언해 줍시다.

 

dp[i][j] = i번째까지 커피를 선택했을 경우 카페인j 를 만들 수 있는 최소값

 

이걸 구하려면 min 값으로 갱신을 해줘야 되는데 2차원으로 풀때 dp[0][1~k]를 0으로 두면 안되고 INF 값으로 두어야지 원하는 값을 도출할 수 있습니다.

 

dp[i][j] = min(dp[i-1][j],dp[i-1][j-w[i]]) 가 될테니까요...

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n, k,arr[110];
int dp[110][100010];

int main()
{
	cin >> n >> k;
	
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int i = 1; i <= k; i++)
		dp[0][i] = (int)1e9;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= k; j++)
		{
			if (j - arr[i] >= 0) {
				dp[i][j] = min(dp[i-1][j], dp[i - 1][j - arr[i]] + 1);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	if (dp[n][k] == (int)1e9)cout << -1;
	else cout << dp[n][k];
	return 0;
}