[c++]백준 1315 - RPG(메모이제이션, dp)

0. [c++] 백준

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

1. 풀이

이 문제 과거에 분명히 본 기억이 나는데, 흠... 일단 다시 풀어보았다.

이 문제에서 메모이제이션으로 cache[str][int]에 현 위치에서 해결 가능한 퀘스트의 개수를 저장해주자.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include<iostream> #include<vector> #include<algorithm>   using namespace std;   int N; int sol; vector<pair<pair<int, int>, int> > quest;   bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {     return (a.first.first + a.first.second) < (b.first.first + b.first.second); }   int cache[1001][1001];   void dp(const int& here_str, const int& here_int) {     int& ret = cache[here_str][here_int];     if (ret != -1) {         return;     }     ret = 0;     int here_pnt = 2;     for (int i = 0; i < N; i++) {         pair<int, int> next = quest[i].first;         int next_pnt = quest[i].second;         if (next.first <= here_str || next.second <= here_int) {             here_pnt += next_pnt;             ret++;         }     }       if (sol < ret)         sol = ret;       here_pnt -= here_str;     here_pnt -= here_int;       for (int i = here_str; i <= min(1000, (here_str + here_pnt)); i++) {         dp(i, min(1000, (here_str - i + here_pnt + here_int)));     }   }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     int a, b, c;     cin >> N;     for (int i = 0; i < N; i++) {         cin >> a >> b >> c;         quest.push_back({ {a,b},c });     }     //sort(quest.begin(), quest.end(), cmp);       //for (int i = 0; i < N; i++) {     //    cout << quest[i].first.first << " " << quest[i].first.second << endl;     //}       for (int i = 0; i < 1001; i++)          for(int j=0;j<1001;j++)             cache[i][j] = -1;            dp(1, 1);     cout << sol;       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!