[BOJ/Gold 3] 백준 24395 명진이의 신년계획(C++)

문제 링크

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

24395번: 명진이의 신년계획

 

문제

카오스 동아리 사람들은 모두 코딩에 미쳐있기 때문에 주기적으로 약을 처방받는다. 동아리의 회장 명진이는 새해를 맞아 이들 모두를 치료하고자 한다.

그들이 걸린 질병은 총 M종류이며 각 질병은 0 이상, 100 이하의 위험도를 지닌다. 회원들은 걸린 질병에 따라 특정 개수의 빨강, 파랑 알약을 처방받는다.

• 처방받는 알약의 수와 위험도가 모두 같은 서로 다른 질병이 존재할 수 있다.
• 하나의 질병에 대해 여러 번 처방받을 수 없다.
• 처방받는 알약의 수는 종류별 50개 이하이며 2종류를 합해 최소 1개 이상이다.

명진이는 신년계획에 따라 학생들의 위험군을 계산해 치료 순서 리스트를 작성하고자 한다.

• 위험군은 해당 학생이 지닐 수 있는 질병들의 위험도 합계의 최대치로 정해진다.
• 리스트는 저위험군 학생부터 나열되며, 위험군이 같을 경우 번호가 앞선 학생이 먼저 나온다.
• 만약 학생이 지닌 알약이 어떠한 처방으로도 만들 수 없는 경우, 해당 학생은 미친 척하는 정상인으로 위험군이 0이다.

N명의 학생이 처방받은 빨강, 파랑 알약의 수가 주어졌을 때, 명진이를 도와 치료 순서 리스트를 작성해보자.

입력

첫째 줄에 N (1 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100)이 공백을 두고 주어진다.

둘째 줄부터 M개의 줄에 걸쳐 M개의 질병에 처방할 빨강, 파랑 알약의 수 Ri , Bi (0 ≤ Ri , Bi ≤ 50, Ri + Bi ≥ 1)와 위험도 Di (0 ≤ Di ≤ 100)가 공백을 두고 주어진다.

M+2번째 줄부터 N 개의 줄에 걸쳐 N 명의 학생이 처방받은 빨강, 파랑 알약의 수 R'i , B'i (0 ≤ R'i , B'i ≤ 50, R'i + B'i  ≥ 1)가 공백을 두고 주어진다.

출력

N개의 줄에 걸쳐 학생 번호와 위험군을 빈칸을 두고 리스트 순서대로 출력한다.

예제 입력 1

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

예제 출력 1

1 6
2 9

1번 학생은 3개의 빨간색 알약과 3개의 파란색 알약을 처방받았다. 해당 알약을 만들 수 있는 경우는

1. 1번 질병 (빨간색 1개, 파란색 1개) + 2번 질병 (빨간색 2개, 파란색 2개)
2. 3번 질병 (빨간색 3개, 파란색 3개)

2가지의 경우가 존재한다. 각각의 경우에 위험도는

1. 1번 질병의 위험도(2) + 2번 질병의 위험도(4) = 6
2. 3번 질병의 위험도(5) = 5

가 되며, 1번 학생의 위험군은 위험도 합계의 최대치인 6이 된다.

2번 학생은 빨간색 알약 5개, 파란색 알약 5개를 처방받았으며, 2번 질병(빨간색 2개, 파란색 2개) + 3번 질병(빨간색 3개, 파란색 3개)의 경우밖에 존재하지 않는다.

예제 입력 2

3 3
0 1 1
0 1 1
1 0 1
1 1
1 2
6 6

예제 출력 2

3 0
1 2
2 3

알고리즘 분류

• 정렬
• 배낭 문제

풀이

학생들이 처방받을 수 있는 빨강 및 파랑 알약의 수는 각각 50개까지다. 따라서, DP[50][50]이라는 2차원 배열을 선언한다. 이것은 빨강 알약 i개와 파랑 알약 j개를 처방받았을 때의 최대 위험도를 의미한다.

이제 냅색 알고리즘을 사용하여 M개의 처방을 탐색하면서 빨강 알약 i개와 파랑 알약 j개를 처방받았을 때의 최대 위험도를 기록해준다.

마지막으로 Answer 벡터에 학생의 번호와 각각의 빨강 알약 및 파랑 알약을 처방받았을 때의 위험도를 pair로 묶어 push하고, 위험도 순으로 오름차순, 위험도가 같으면 학생의 번호 순으로 오름차순 정렬한 후 학생들의 정보를 번호, 위험도 순으로 출력한다.

코드

#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 100001
#define MAX_M 101
#define MAX_RB 51
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
int R[MAX_M], B[MAX_M], D[MAX_M];
int DP[MAX_RB][MAX_RB];
vector<pair<int, int> > Answer;

bool Comp(pair<int, int> A, pair<int, int> B) {
	if (A.second == B.second) {
		return (A.first < B.first);
	}
	return (A.second < B.second);
}

void Init() {
	for (int i = 0; i < MAX_RB; i++) {
		for (int j = 0; j < MAX_RB; j++) {
			DP[i][j] = -1;
		}
	}
	DP[0][0] = 0;
}

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

void Settings() {
	for (int i = 1; i <= M; i++) {
		for (int j = 50; j >= 0; j--) {
			for (int k = 50; k >= 0; k--) {
				if ((j - R[i] >= 0) && (k - B[i] >= 0) && (DP[j - R[i]][k - B[i]] != -1)) {
					DP[j][k] = max(DP[j][k], DP[j - R[i]][k - B[i]] + D[i]);
				}
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		int RR, BB;
		cin >> RR >> BB;
		Answer.push_back(make_pair(i, (DP[RR][BB] == -1 ? 0 : DP[RR][BB])));
	}
	sort(Answer.begin(), Answer.end(), Comp);
}

void Find_Answer() {
	for (int i = 0; i < Answer.size(); i++) {
		cout << Answer[i].first << " " << Answer[i].second << "\n";
	}
}

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

	return 0;
}