[BOJ/Gold 5] 백준 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 ≤ Ci ≤ 1,000

예제 입력 1

4 5
1 1 3 2

예제 출력 1

2

예제 입력 2

5 5
1 1 3 2 5

예제 출력 2

1

예제 입력 3

5 7
1 1 1 1 1

예제 출력 3

-1

알고리즘 분류

• 배낭 문제

풀이

마셔야 하는 커피의 최소 개수를 구하는 것이기 때문에, 우선 DP[100000]의 모든 원소를 1e9로 초기화시킨다.

DP[100000]은 섭취한 카페인이 i일 때 마신 커피의 최소 개수를 의미한다.

이제 첫 번째 커피부터 탐색하면서 첫 번째 커피를 마셨을 때와 안 마셨을 때의 마신 커피의 개수를 비교해서 각 카페인 수치마다 마신 커피의 최소 개수를 기록해준다.

마지막으로 DP[K], 즉 카페인의 수치가 K일 때 마신 최소의 커피 개수를 출력한다. 이 때 1e9라면 정확히 K만큼의 카페인을 섭취할 수 없다는 뜻이므로 -1을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX_N 101
#define MAX_K 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, K;
int C[MAX_N];
int DP[MAX_K];
int Answer = 0;

void Init() {
	for (int i = 0; i < MAX_K; i++) {
		DP[i] = INF;
	}
}

void Input() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> C[i];
	}
}

void Settings() {
	Init();
	DP[0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = K; j >= C[i]; j--) {
			if (j - C[i] >= 0) {
				DP[j] = min(DP[j], DP[j - C[i]] + 1);
			}
		}
	}
}

void Find_Answer() {
	if (DP[K] == INF) {
		cout << -1 << "\n";
	}
	else {
		cout << DP[K] << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}