[백준 22115] 창영이와 커피 (C++)

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

22115번: 창영이와 커피

문제

---

창영이는 커피를 좋아한다. 회사에 도착한 창영이는 아침 커피를 즐기려고 한다.

회사에는 N개의 커피가 각각 하나씩 준비되어 있고, 각 커피에는 카페인 함유량 Ci가 있다.

창영이는 N개의 커피 중 몇 개를 골라 정확히 K만큼의 카페인을 섭취하려고 한다.

창영이가 정확히 K만큼의 카페인을 섭취하기 위해서는 최소 몇 개의 커피를 마셔야 할까?

입력

---

첫째 줄에 커피의 개수 N, 창영이가 섭취해야 하는 카페인의 양 K가 주어진다.

둘째 줄에 N개 커피의 카페인 함유량 Ci가 주어진다.

출력

---

창영이가 K만큼의 카페인을 섭취하기 위해 마셔야 하는 커피의 최소 개수를 출력한다.

만약 정확히 K만큼의 카페인을 마실 수 없으면 -1을 출력한다.

제한

---

• 1 ≤ N ≤ 100 
• 0 ≤ K ≤ 100,000
• 1 ≤ C_i ≤ 1,000

 

문제 풀이

---

배낭 문제.

2차원 배열을 생성하고 i번째 커피까지 있을 때 카페인 1 ~ N까지 커피의 최소 개수를 채우면 된다.

예제 입력 1 1 3 2를 예시로 들어보자.

 

(오름차 순 정렬된 상태이다.)

i가 0일 때, 카페인 1을 섭취할 수 있고, 2~5는 섭취 불가능하다.

	1	2	3	4	5
1	1	MAX	MAX	MAX	MAX

 

 

i가 1일 때, 카페인 1을 추가로 섭취할 수 있다. 카페인 1은 여전히 최소 한 개 먹어야 얻을 수 있다.

카페인 2는 i=1인 커피를 마시고, i=0인 커피를 마셔야 얻을 수 있다. 따라서 2를 채워준다. 나머지는 얻을 수 없으므로 MAX를 채워준다.

	1	2	3	4	5
1	1	MAX	MAX	MAX	MAX
1	1	2	MAX	MAX	MAX

 

 

i=2일 때, 카페인 2를 추가로 섭취할 수 있다. 카페인 2는 i=2인 커피를 한 잔 마시면 얻을 수 있으므로 1로 갱신할 수 있다.

카페인 3은 i=2인 커피를 마시고, 이전까지의 커피에서 카페인 1을 얻으면 된다. 이는 1 + 배열[i-1][0]로 표현된다.

카페인 4는 i=2인 커피를 마시고, 이전까지의 커피에서 카페인 2를 얻으면 된다. 이는 1 + 배열[i-1][1]로 표현된다.

arr[i] \ 카페인	1	2	3	4	5
1	1	MAX	MAX	MAX	MAX
1	1	2	MAX	MAX	MAX
2	1	1	2	3	MAX

 

 

i=3일 때 카페인 3을 추가로 섭취할 수 있다. 카페인 3은 i=3인 커피를 한 잔 마시면 얻을 수 있으므로 1로 갱신할 수 있다.

카페인 4는  i=2일 때 커피를 3잔 마시면 최솟값이었다. 하지만 i=3인 커피를 마시고, 이전까지의 커피에서 카페인 1을 얻을 수도 있는데, 이것이 2잔으로 최솟값이 되므로 2로 갱신된다.

카페인 5는 i=3인 커피를 마시고, 이전까지의 커피에서 카페인 2를 얻으면 된다. 이는 1+ 배열[i-1][1]으로 표현된다.

arr[i] \ 카페인	1	2	3	4	5
1	1	MAX	MAX	MAX	MAX
1	1	2	MAX	MAX	MAX
2	1	1	2	3	MAX
3	1	1	1	2	2

 

 

즉, 배열의 열(반복문에서 j가 될 것이다)이 커피에서 얻을 수 있는 카페인(arr[i])의 숫자와 같다면 한잔을 마실 수 있으므로 그 행의 칸[i][j]은 1로 채워진다.

만약 커피에서 얻을 수 있는 카페인(arr[i])보다 작다면 그 행의 커피를 마실 수 없으므로 그 행의 칸[i][j]은 이전 행의 값과 같다.

만약 커피에서 얻을 수 있는 카페인(arr[i])보다 크다면 이전 행에서의 커피 개수를 그대로 가져올 수도 있고([i-1][j]),

현재 행의 커피를 마시고 [i - 1][j - arr[i]] 카페인을 추가로 얻을 수도 있다. 두 값을 비교하여 [i][j]를 더 작은 값으로 채워주면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#define MAX 10000000
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	int** dp = new int*[N];
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		dp[i] = new int[M+1];
		cin >> arr[i];
		for (int j = 0; j < M+1; j++)
		{
			dp[i][j] = MAX;
		}
	}
	if (M == 0)
	{
		cout << 0 << "\n";
	}
	else
	{
		sort(arr, arr + N);
		for (int i = 0; i < M + 1; i++)
		{
			if (i == arr[0])
			{
				dp[0][i] = 1;
			}
		}
		for (int i = 1; i < N; i++)
		{
			for (int j = 0; j < M + 1; j++)
			{
				if (j < arr[i])
				{
					dp[i][j] = dp[i - 1][j];
				}
				else if (j == arr[i])
				{
					dp[i][j] = 1;
				}
				else
				{
					dp[i][j] = min(dp[i - 1][j], 1 + dp[i - 1][j - arr[i]]);
				}
			}
		}
		if (dp[N - 1][M] == MAX)
		{
			cout << -1 << "\n";
		}
		else
		{
			cout << dp[N - 1][M] << "\n";
		}
	}
	return 0;
}