[백준] 1315번 RPG (C++)

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

 

 

이 문제는 N개의 퀘스트가 주어질때 각각의 퀘스트에 필요한 요구치가 주어진다 이는 STR[i], INT[i]가 주어지며 퀘스트를 완료하기 위해서 현재 나의 스텟 중에 하나 이상이 퀘스트가 요구하는 스텟보다 크면 완료할 수 있으며 보너스로 스텟을 찍을 수 있는 포인트를 준다.

이때 최대로 완료할 수 있는 퀘스트의 개수를 구하는 문제이다.

 

스스로 해결: ❌

 

접근방법

어느정도 dp를 사용해서 풀어야하는 것은 알았지만 식을 어떻게 세워야할줄 몰랐다. 현재 내가 할 수 있는 행동은 각 퀘스트마다 내 스텟과 비교하여 완료할 수 있으면 다음퀘스트를 완료할 수 있는 가능성이 높아지기 때문에 무조건 완료하는것이 좋다고 생각하였다 또한 퀘스트 완료후 보너스 스텟에 대해 0부터 i까지 분배를 하여 모든 경우 찍어서 아직 완료하지 않은 퀘스트들을 세는 행동을 해야 한다.

 

결국 dp[i][j] = STR 이 i이고 INT가 j일때 완료할 수 있는 퀘스트의 최대 개수

라는 식을 세울 수 있었지만 코드로 작성을 하지는 못했다.

 

https://blog.naver.com/jhc9639/221402814267

 

해당 블로그를 참고하여 코드를 작성할 수 있었고 내가 구현 못한 부분을 발견할 수 있었다.

 

1. STR[i], INT[j] 인 상태에서 완료할 수 있는 퀘스트 확인

2. 보너스 스텟을 누적하여 저장

3. 0부터 보너스 스텟까지 스텟을 배분할 수 있는 모든 경우를 찾기

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

struct Tree {
    int Node, left, right;
};

const int INF = 1e9;
const int MAX = 20001;
const int D = 2000000;
const int MOD = 10007;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
vector<tuple<int, int, int>> v;
int dp[1001][1001];

int func(int STR, int INT) {
    int &ret = dp[STR][INT];

    if(ret != -1) return ret;

    ret = 0;
    int pnt = 0;

    // 현재 완료할 수 있는 퀘스트 개수 세기
    for(int i = 0; i < N; i++) {
        int str = get<0>(v[i]);
        int intr = get<1>(v[i]);
        int pt = get<2>(v[i]);

        if(STR >= str || INT >= intr) {
            pnt += pt;
            ret++;
        }
    }

    int freepnt = pnt - (STR - 1) - (INT - 1);

    for(int i = 0; i <= freepnt; i++) {
        int nextstr = min(1000,STR + freepnt - i);
        int nextint = min(1000, INT + i);

        ret = max(ret, func(nextstr, nextint));
    }

    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    cin >> N;

    for(int i = 0; i < N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
    }

    memset(dp, -1, sizeof(dp));

    cout << func(1, 1);
}