백준 1315 RPG

백준 1315 RPG

C++17의 

auto && [a, b, c] = tuple<int, int, int> t;

구문을 적극 활용

solve(i,j)는 

str가 i, int가 j일 때, 이 이후로 내가 깰 수 있는 최대갯수의 퀘스트

이다.

solve(i,j)에서 현재 스텟에서 깰 수 있는 퀘스트 갯수를 새고

그 퀘스트를 깻다고 표시한 뒤

깰 수 있는 퀘스트들의 포인트들의 합으로 스탯을 배분하여

solve()를 재귀로 호출한다.

이때, 재귀로 들어오기 전에 깻던 퀘스트들은 또다시 깨면 안되기 때문에 

깨지 않은 퀘스트만 깨고, 

다시 위에서 설명한 것처럼 퀘스트 포인트 합으로 스탯 배분 후 다시 재귀 호출을 한다

그리고 재귀호출이 모두 끝나서 리턴하여 본래 함수로 되돌아 오면

스탯을 배분한 수많은 상황중에서 가장 많이 깰 수 있는 퀘스트의 갯수를 max로 구하여

그 값을 dp에 메모이제이션 해주고,

내가 깻던 퀘스트를 다시 안깻다고 표시해준 다음

리턴을 해준다

깻던 퀘스트를 안깻다고 표시해주는 이유는, 

리턴하여 돌아가면 스탯이 줄어들고, 퀘스트를 안깬 샘이 되기 때문이고

리턴하여 돌아갔을때 또다시 스탯을 배분하여 새로 퀘스트를 몇개 더 깰수 있는지 계산해야 하기 때문이다.

이때 isVisit는 내가 새로 깬 퀘스트들의 인덱스가 벡터로 들어가고

isClear는 내가 재귀를 호출하며 깨왔던 퀘스트들이 각각 true와 false로 저장되어 있다.

아, 그리고

str과 int는 1천을 넘길 필요가 없다 (왜냐하면 모든 퀘스트의 스탯제한은 1천이기 때문)

따라서 만랩을 1천이라고 생각하면 되므로 dp는 [1000][1000]만 있으면 된다.

또한 이것을 이용하여 힘과 지능 둘중의 하나의 스탯만 만렙에 도달하면 모든 퀘스트를 깰 수 있으므로

퀘스트 갯수를 print하고 exit()로 알고리즘을 끝내는 방법이 또 있다.

#define FLAT(INPUT) ((INPUT) >= 1001 ? 1000 : (INPUT))

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string.h>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stack>
#include <tuple>

using namespace std;

int memo[1001][1001];
int N = 100;
vector<tuple<int, int, int>> quest;
vector<int> canPnt;

bool isClear[101];


bool comp(tuple<int, int, int> a, tuple<int, int, int> b) {
	auto[ax, ay, az] = a;
	auto[bx, by, bz] = b;

	if (ax < bx) return true;
	else if (ax == bx) {
		if (ay < by) return true;
		else if (ay == by) return az < bz;
		else return false;
	}
	else return false;
}

int solve(int _str, int _int) {
	//cout << _str << ", " << _int << endl;
	int & ret = memo[_str][_int];
	if (ret != -1) return ret;
	if (_str < 1 || _int < 1) return 0;

	int canSuc = 0;
	int canPnt = 0;
	vector<int> *isVisit = new vector<int>();

	for (int i = 0; i < N; i++) {
		auto &&[st, in, pn] = quest[i];
		if (_str >= st || _int >= in) {
			if (!isClear[i]) {
				isClear[i] = true;
				isVisit->push_back(i);
				canPnt += pn;
			}
			canSuc++;
		}
	}

	ret = canSuc;

	for (int i = 0; i <= canPnt; i++) {
		ret = max(ret, solve(FLAT((_str + i)), FLAT((_int + (canPnt - i)))));
	}

	for (int &s : *isVisit) {
		isClear[s] = false;
	}

	return ret;	
}

int main() {
	scanf("%d", &N);

	int a, b, c;
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d", &a, &b, &c);
		quest.push_back(make_tuple(a, b, c));
		isClear[i] = false;
	}

	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) {
			memo[i][j] = -1;
		}
	}

	//sort(quest.begin(), quest.end(), comp);

	int result = solve(1, 1);

	printf("%d\n", result);

	return 0;
}