[BOJ/Gold 4] 백준 6066 Buying Hay(C++)

문제 링크

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

6066번: Buying Hay

 

문제

Farmer John is running out of supplies and needs to purchase H (1 <= H <= 50,000) pounds of hay for his cows.

He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N. Supplier i sells packages that contain P_i (1 <= P_i <= 5,000) pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each supplier has an unlimited number of packages available, and the packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least H pounds of hay.

입력

• Line 1: Two space-separated integers: N and H
• Lines 2..N+1: Line i+1 contains two space-separated integers: P_i and C_i

출력

• Line 1: A single integer representing the minimum cost FJ needs to pay to obtain at least H pounds of hay.

예제 입력 1

2 15
3 2
5 3

예제 출력 1

9

힌트

FJ can buy three packages from the second supplier for a total cost of 9.

알고리즘 분류

• 배낭 문제

풀이

DP[100][55555]이라는 2차원 배열을 선언한다. 이것은 i번째 패키지를 탐색했을 때, j파운드만큼의 건초를 구입한 최소 비용을 의미한다. 최소 비용을 구하는 것이기 때문에 먼저 모든 원소를 1e9로 초기화시켜준다. 그리고 j를 최대 50,000이 아니라 그보다 더 큰 수로 정한 이유는, 50,000으로 정하면 50,000파운드만큼의 건초를 구입하는 데 드는 최소 비용을 더 구해낼 수 없기 때문이다.

이후에는 첫 번째 패키지부터 탐색하면서 j파운드만큼의 건초를 구입하는 데 드는 비용의 최솟값을 기록해나간다.

마지막으로, H파운드 이상의 건초를 구입하는 데 드는 최소의 비용을 구하는 것이므로 H부터 55,555까지, i파운드만큼의 건초를 구입하는 데 드는 최소 비용(DP[N][i]) 중에서 최솟값을 구한다.

코드

#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_H 55555
#define LL long long
#define INF 1e9

using namespace std;
int N, H;
int P[MAX_N], C[MAX_N];
int DP[MAX_N][MAX_H];
int Answer = INF;

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

void Settings() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < MAX_H; j++) {
			DP[i][j] = INF;
		}
	}
	DP[0][0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < MAX_H; j++) {
			if (j - P[i] >= 0) {
				DP[i][j] = min(DP[i - 1][j], DP[i][j - P[i]] + C[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
		}
	}
	for (int i = H; i < MAX_H; i++) {
		Answer = min(Answer, DP[N][i]);
	}
}

void Find_Answer() {
	cout << Answer << "\n";
}

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

	return 0;
}