백준 1315번 RPG

문제 링크입니다: https://www.acmicpc.net/problem/1315

스탯을 올릴 수 있는 포인트라는 개념이 있었기 때문에 상당히 까다로웠던 DP 문제였습니다.

알고리즘은 아래와 같습니다.

1. 힘과 지능은 모두 1로 시작합니다.

2. 현재 힘과 지능을 통해 깰 수 있는 퀘스트의 수를 구합니다.

-> 이 때, 새로 클리어하는 퀘스트의 보상(포인트)의 누적합을 구합니다.

3. 2번에서 구한 포인트의 누적합을 힘과 지능에 투자할 수 있는 모든 경우의 수를 고려하여 다시 재귀함수를 호출합니다.

4. 3번에서 구한 퀘스트의 수 중 최대값을 반환합니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 100 + 1;

 

int N;

pair<pair<int, int>, int> arr[MAX]; ///힘, 지능, 포인트

int cache[1000 + 1][1000 + 1]; //힘, 지능

bool visited[MAX];

 

int maxQuest(int strength, int intelligence)

{

        int &result = cache[strength][intelligence];

        if (result != -1)

                 return result;

 

        int point = 0; //추가 스탯 포인트

        int cnt = 0; //클리어한 퀘스트

       

        vector<int> v;

        for (int i = 0; i < N; i++)

        {

                 //클리어할 수 있는 퀘스트

                 if (arr[i].first.first <= strength || arr[i].first.second <= intelligence)

                 {

                         //이미 클리어하지 않은 퀘스트들

                         if (!visited[i])

                         {

                                 visited[i] = true;

                                 v.push_back(i);

                                 point += arr[i].second;

                         }

                         cnt++;

                 }

        }

        result = cnt;

 

        //힘과 지능에 올릴 수 있는 모든 경우의 수 고려

        for (int i = strength; i <= min(1000, strength + point); i++)

                 result = max(result, maxQuest(i, min(1000, intelligence + (point - (i - strength)))));

 

        //초기화

        for (int i = 0; i < v.size(); i++)

                 visited[v[i]] = false;

 

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i].first.first >> arr[i].first.second >> arr[i].second;

 

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

        cout << maxQuest(1, 1) << "\n";

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~