백준 1315 RPG 풀이 (c++)

문제

준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.

게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.

모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.

준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 퀘스트의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 STR[i], INT[i], PNT[i]가 주어진다. 이 숫자는 모두 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

struct game
{
	int x, y, c;
};
vector<game> a;
int N, dp[1001][1001];
bool visited[101];

int rpg(int STR, int INT) 
{
	int& iResult = dp[STR][INT];
	if (iResult != -1) return iResult;

	iResult = 0;
	int pnt = 0;
	vector<int> v;
	for (int i = 0; i < N; i++) 
	{
		if (a[i].x <= STR || a[i].y <= INT) 
		{
			iResult++;
			if (!visited[i]) 
			{
				visited[i] = true;
				pnt += a[i].c;
				v.push_back(i);
			}
		}
	}

	for (int p = 0; p <= pnt; p++) 
	{
		int nextSTR = min(1000, STR + p);
		int nextINT = min(1000, INT + pnt - p);
		iResult = max(iResult, rpg(nextSTR, nextINT));
	}
	for (int here : v)
		visited[here] = false;

	return iResult;
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; i++) 
	{
		int STR, INT, PNT;
		cin >> STR >> INT >> PNT;
		a.push_back({ STR, INT, PNT });
	}
	memset(dp, -1, sizeof(dp));
	cout << rpg(1, 1);
}

dp 이용 풀이