[BOJ/Gold 4] 백준 14855 만두 가게 사장 박승원(C++)

문제 링크

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

14855번: 만두 가게 사장 박승원

 

문제

승원이는 오늘 가게에서 판매할 만두를 만들려고 한다. 만두는 만두피에 만두 속을 넣어서 예쁘게 빚어서 만드며, 만두피는 밀가루로 만든다.

가게에서 판매하는 만두는 총 m종류가 있으며, 현재 밀가루는 n그램 있다. 만두의 종류는 1번부터 m번까지 번호가 매겨져 있다.

i번 만두를 만들 수 있는 만두 속은 ai그램이 남아있으며, 만두 하나를 만들기 위해서 bi그램의 만두 속이 필요하다. i번 만두의 만두피는 ci그램의 밀가루로 만들어야 하며, 만두 하나당 판매 금액은 di원이다.

스페셜 메뉴로 만두 속 없이 만두 피만 가지고 만들 수 있는 만두도 있다. 이 만두는 하나를 만드는데 c0그램의 밀가루가 필요하고, 한 개당 d0원에 판매할 수 있다.

승원이가 만들 수 있는 만두 금액의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n, m, c0, d0 (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c0, d0 ≤ 100)이 주어진다.

다음 m개의 줄에는 ai, bi, ci, di (1 ≤ ai, bi, ci, di ≤ 100)가 주어진다.

출력

첫째 줄에 승원이가 만들 수 있는 만두 금액의 합의 최댓값을 출력한다.

예제 입력 1

10 2 2 1
7 3 2 100
12 3 1 10

예제 출력 1

241

예제 입력 2

100 1 25 50
15 5 20 10

예제 출력 2

200

힌트

첫 번째 에제의 경우에는 1번 만두를 2개 만들고, 2번 만두를 4개 만들고, 스페셜 만두를 1개 만들면 되고, 두 번째 예제의 경우에는 스페셜 만두를 4개 만들면 된다.

알고리즘 분류

• 배낭 문제

풀이

M+1개의 만두의 각각의 개수들이 1개가 아닌데, 그 개수가 정해져 있으므로, Bounded 냅색 알고리즘을 사용해야 한다.

하지만 아무리 조사해봐도 아이디어가 떠오르지 않아 고수분께 자문을 구해서 해결하였다.

DP[10000][10]이라는 2차원 배열을 선언한다. 이것은 i번째 만두를 j개까지 만들었을 때, k그램만큼의 밀가루를 사용했을 경우 벌어들일 수 있는 최대의 금액을 의미한다.

또한, 스페셜 만두를 제외한 만두들의 개수는 A/B와 N/C 양쪽 값 중 최솟값이 된다. 본인은 처음에 이것을 생각하지 못 하고 무조건 A/B개까지 만들 수 있다고 생각하여서 굉장히 아쉬웠다.

문제 파악이 완료되었다면 일반적인 0-1 냅색 알고리즘처럼 코드를 구현해서 해결하고 벌어들일 수 있는 금액의 최댓값을 구한다.

지금까지는 단순 0-1 냅색 알고리즘 관련 문제들만 해결했으나, 이 문제는 Bounded 냅색 알고리즘에 관하여 파악할 수 있어서 괜찮은 문제라고 생각이 되었다.

코드

#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 1001
#define MAX_M 11
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int A[MAX_M], B[MAX_M], C[MAX_M], D[MAX_M];
int Bound[MAX_M];
int DP[MAX_M * MAX_N][MAX_N];
int IDX = 1;
int Answer = 0;

void Input() {
	cin >> N >> M >> C[0] >> D[0];
	for (int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}
}

void Settings() {
	Bound[0] = N / C[0];
	for (int i = 1; i <= M; i++) {
		Bound[i] = min((A[i] / B[i]), (N / C[i]));
	}
	for (int i = 0; i <= M; i++) {
		for (int j = 1; j <= Bound[i]; j++) {
			for (int k = N; k >= 0; k--) {
				if (k - C[i] >= 0) {
					DP[IDX][k] = max(DP[IDX - 1][k], DP[IDX - 1][k - C[i]] + D[i]);
				}
				else {
					DP[IDX][k] = DP[IDX - 1][k];
				}
				Answer = max(Answer, DP[IDX][k]);
			}
			IDX++;
		}
	}
}

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

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

	return 0;
}