BOJ 백준 1315번 RPG

 

BOJ 백준 1315 RPG

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

1315번: RPG

 

RPG 게임에서 캐릭터의 스탯으로 힘(STR)과 지력(INT) 2가지가 존재하고, 처음 생성했을 때 스탯은 모두 1이다. 게임에는 하나 당 한 번만 깰 수 있는 총 N개의 퀘스트가 존재한다. i번째 퀘스트를 깨는 데 필요한 STR를 STR[i], INT를 INT[i]라고 할 때, 이를 깨려면 캐릭터의 STR가 STR[i] 이상이거나 캐릭터의 INT가 INT[i] 이상이라는 조건을 만족해야 한다. i번째 퀘스트를 깨면 캐릭터의 STR 또는 INT를 올릴 수 있는 스탯 포인트 PNT[i]를 얻는다. 퀘스트를 깨는 순서와 어떻게 스탯을 분배하느냐는 원하는대로 가능할 때, 깰 수 있는 퀘스트 개수의 최댓값을 구해야 한다.

 

 

 

문제 해결을 위한 알고리즘으로 동적 프로그래밍(Dynamic Programming), 비트 마스킹을 이용한 동적 프로그래밍 그리고 탐욕 알고리즘(Greedy Algorithm)을 생각했다.

 

비트 마스킹을 이용한 동적 프로그래밍으로 해결할 경우 N개의 퀘스트 중 이제까지 깬 퀘스트가 무엇인지에 관한 정보를 비트로 저장해야 할 것이다. 그렇지만 N의 제한이 너무 커서 퀘스트 순서까지 비트로 메모이제이션 할 수 없다. 비트마스킹으로 해결하려면 N의 최대 제한인 50만큼 길이의 비트가 필요한데, 이는 2^50 = 10^5 크기의 배열이 필요하다는 의미이다. 이것만 필요하면 상관 없지만, 문제는 현재 캐릭터 스탯 상태를 같이 저장해야 하므로 메모리 초과가 발생할 것이다.

 

탐욕 알고리즘을 고려하면 단순히 매번 스탯을 많이 주는 퀘스트를 먼저 깨는 것이 과연 전체적으로 최적화된 답을 보장할 수 있는지 고민해야 한다. 퀘스트가 준 포인트를 어떠한 스탯에 얼만큼 투자하느냐에 따라 답이 달라지므로 탐욕 알고리즘으로 푸는 것도 쉽지 않다.

 

그런데 사실 푸는 과정에서 이제까지 퀘스트를 깬 순서를 고려할 필요는 없어 보인다. 왜냐하면 캐릭터의 현재 STR와 INT만 알면 깰 수 있는 퀘스트 수는 자동적으로 정해지기 때문이다. 문제에서 퀘스트를 깨는 데 필요한 STR가 캐릭터의 STR 이하이거나, 퀘스트를 깨는 데 필요한 INT가 캐릭터의 INT 이하이면 이에 해당하는 퀘스트는 모두 깰 수 있다고 했다. 어떤 한 퀘스트를 깬다고 해서 캐릭터의 STR 또는 INT 값이 소모되는 게 아니라는 점을 유의해야 한다. 그러므로 동적 프로그래밍에서 현재 캐릭터의 STR와 INT 상태만 메모이제이션 해주면 되는 것이다.

 

DP[STR][INT]: 힘이 STR이고 지력이 INT인 상태가 될 수 있는가?

LeftPoint[STR][INT]: 힘이 STR이고 지력이 INT인 상태에서 깰 수 있는 모든 퀘스트를 깼을 때 남는 포인트

Solved[STR][INT]: 힘이 STR이고 지력이 INT일 때 깰 수 있는 퀘스트의 최대 수

 

위의 세 개의 배열을 사용하여 동적 프로그래밍으로 해결 가능할 것이다.

 

현재 캐릭터의 스탯 값이 힘은 STR이고 지력은 INT라고 하자.

 

 

 

1) 전 상태에서 힘을 1만큼 올려서 현재 상태로 만들 수 있는 경우

DP[STR - 1][INT] == true && LeftPoint[STR - 1][INT] > 0 (단, STR >= 1)

 

 

2) 전 상태에서 지력을 1만큼 올려서 현재 상태로 만들 수 있는 경우

DP[STR][INT - 1] == true && LeftPoint[STR][INT - 1] > 0 (단, INT >= 1)

 

 

→ 위의 둘 중 하나의 조건이라도 만족하면 현재 상태를 만들 수 있으므로

DP[STR][INT] == true

 

 

 

캐릭터의 힘이 STR이고 지력이 INT인 경우를 모두 살펴보면서 각 경우에 깰 수 있는 퀘스트는 총 몇 개인지 먼저 구하고, 위에서 정리한 과정처럼 해당 경우가 과연 가능한 경우인 것인지 구하면 된다. 그러면 고려해야 하는 캐릭터 스탯 값의 상한선이 있어야 하는데 이는 어느 정도로 설정하면 좋을까? 문제에서 퀘스트를 깨는 데 필요한 스탯의 최댓값이 1000이라고 했다. 또한 퀘스트를 깬다고 해서 캐릭터의 스탯을 소모하는 것이 아니라고 했다. 따라서 STR가 1000 이하이고 INT가 1000 이하인 경우만 고려해도 문제를 구하는 데 지장이 없다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N_MAX = 1000;

struct Quest {
    int s, i, p;
};

int n;
bool possible[N_MAX + 1][N_MAX + 1];
int left_point[N_MAX + 1][N_MAX + 1];
int solved[N_MAX + 1][N_MAX + 1];

vector<Quest> quest;

int main(){
    scanf("%d", &n);
    
    quest.resize(n);
    
    for (int i = 0; i < n; i++){
        scanf("%d %d %d", &(quest[i].s), &(quest[i].i), &(quest[i].p));
    }
    
    for (int s = 1; s <= N_MAX; s++){
        for (int i = 1; i <= N_MAX; i++){
            int point_sum = 0;
            for (int j = 0; j < n; j++){
                if (quest[j].s <= s || quest[j].i <= i) {
                    point_sum += quest[j].p;
                    solved[s][i] += 1;
                }
            }
            
            left_point[s][i] = point_sum - (s - 1) - (i - 1);
            
            if (s == 1 && i == 1) {
                possible[s][i] = true; continue;
            }
            
            if (possible[s - 1][i] && left_point[s - 1][i] > 0 && s - 1 > 0){
                possible[s][i] = true; continue;
            }
            if (possible[s][i - 1] && left_point[s][i - 1] > 0 && i - 1 > 0) {
                possible[s][i] = true; continue;
            }
        }
    }
    
    int ans = 0;
    for (int s = 1; s <= N_MAX; s++){
        for (int i = 1; i <= N_MAX; i++){
            if (possible[s][i]){
                ans = max(ans, solved[s][i]);
            }
        }
    }
    printf("%d\n", ans);
    
    return 0;
}