캐릭터는 $CharStr, CharInt$ 두 가지 스탯을 가지고 있다.
퀘스트가 N개 존재하는데 $(QuestStr <= CharStr) || (QuestInt <= CharInt)$이면
퀘스트를 깨서 포인트를 얻을 수 있다.
포인트는 마음대로 스탯을 올릴 수 있다.
최대로 깰 수 있는 퀘스트의 개수를 구하는 문제이다.
스탯을 기준으로 2차원 dp를 잡으면 해결할 수 있다.
$Str$과 $Int$가 주어졌을 때 깰 수 있는 퀘스트는 정해져있으므로
깨지 않은 퀘스트들에 대하여 포인트들의 합을 구하였다.
그 포인트들의 합으로 다음 스탯을 구해서 재귀로 돌렸다.
(다음 스탯을 구하는 부분에서 잘못생각해서 3번이나 틀렸다.)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct Quest {
int s, i, point;
};
int N;
Quest quest[101];
bool visit[101];
int dp[1001][1001];
int solve(int Str, int Int) {
int &ret = dp[Str][Int];
if (ret != -1) return ret;
ret = 0;
int save_point = 0, cnt = 0;
vector<int> save;
for (int n = 0;n < N;n++) {
if (quest[n].s <= Str || quest[n].i <= Int) {
if (!visit[n]) {
visit[n] = true;
save.push_back(n);
save_point += quest[n].point;
}
cnt++;
}
}
ret = cnt;
for (int s = Str; s <= min(1000, Str + save_point);s++) {
int i = min(1000, Int + save_point - (s - Str));
ret = max(ret, solve(s, i));
}
for (int &s : save) visit[s] = false;
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0;n < N;n++)
scanf("%d%d%d", &quest[n].s, &quest[n].i, &quest[n].point);
printf("%d\n", solve(1, 1));
return 0;
}
| cs |
현재 스탯으로 깰 수 있는 퀘스트의 스탯을 좌표평면상으로 그리면 'ㄴ'자 모양이 되는점을
이용하여 푼 풀이도 있었다.
댓글 없음:
댓글 쓰기