RPG( BOJ 1315 )

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

1315번: RPG

 

문제 파악하기

경험치를 힘(STR)과 지력(INT)에 적절히 투자해서 클리어할 수 있는 퀘스트의 최댓값을 구하는 문제입니다. 각각의 퀘스트는 클리어를 할 수 있는 힘과 지력의 제한이 있으며, 캐릭터의 힘과 지력 중 어느 한 곳의 능력치가 특정 퀘스트의 힘과 지력 제한보다 크거나 같다면 해당 퀘스트를 클리어하고 경험치를 얻을 수 있습니다. 문제를 해결할 수 있는 가장 단순한 알고리즘은 현재 지닌 힘과 지력을 기준으로 퀘스트마다 해결 여부를 확인하면서 새롭게 퀘스트를 해결하고, 경험치를 올려서 다시 퀘스트를 확인하는 알고리즘을 떠올릴 수 있습니다. 하지만 이 방법은 주어진 퀘스트의 개수(N)가 50개이기 때문에 특정 퀘스트를 처리했는지 확인하는 비트마스킹 기법을 활용할 수 없어 효율적인 알고리즘이 될 수 없습니다. 하지만, 문제를 잘 분석해보면 어떤 퀘스트를 처리했는지 꼭 저장할 필요가 없다는 결론을 도출할 수 있습니다.

 

문제 해결하기

그렇다면 왜 퀘스트의 클리어 여부를 기록할 필요가 없을까요? 이는 모든 퀘스트의 클리어 여부가 캐릭터의 힘과 지력에 의해 결정되기 때문입니다. 캐릭터의 힘과 지력이 (a, b)라고 표현할 때, (a, b)가 클리어하여 얻을 수 있는 포인트의 크기는 항상 정해져있으며, 순서에 의해 클리어할 수 있는 퀘스트의 종류가 바뀌지 않습니다. 따라서, (a, b)를 기준으로 클리어할 수 있는 퀘스트의 수와 클리어 시 얻게 되는 경험치의 총합을 가지고 충분히 탐색을 할 수 있습니다. 얻게 되는 총 경험치에서 (1, 1)에서 (a, b)까지 이동하는데 필요한 경험치를 제외하면 현재 투자할 수 있는 경험치가 되며, 이를 힘과 지력에 나누어 투자하면서 탐색을 진행하면 됩니다. 예시와 함께 자세히 살펴봅시다.

 

첫 번째 입력 예시를 통해 하나씩 살펴봅시다. 맨 처음 캐릭터의 능력치는 (1, 1)입니다. 그리고 여기서 클리어할 수 있는 퀘스트는 1개이며, 얻을 수 있는 경험치는 총 2입니다. 여기서, 우리는 투자할 수 있는 경험치가 2라는 걸 알 수 있으며, 이를 통해 (1, 1)에서 { (3, 1), (2, 2), (1, 3) }, 총 3가지 경우에 대해 탐색할 수 있습니다. 그리고, 지금까지 클리어한 퀘스트의 개수를 파악해서 결괏값과 비교하면 됩니다. 만약 여기서 (3, 1)로 탐색했다면 또다시 투자할 수 있는 경험치의 양을 구한 다음, 새로운 탐색을 할 수 있는지 확인하고 지금까지 클리어한 퀘스트의 수를 결괏값과 비교하면 됩니다.

 

이렇게 캐릭터의 능력치를 기준으로 퀘스트의 클리어 여부와 얻게되는 경험치를 파악한 다음, 나올 수 있는 모든 경우를 파악하면 정답을 구할 수 있습니다. 다만, 능력치가 1,000을 넘어갈 수 있다는 점을 기억하고 꼭 예외처리를 해주어야 정확한 정답을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <utility>
#define NMAX 1010
#define PAIR pair< int, int >
using namespace std;
 
int N, a, b, c;
vector< pair< PAIR, int > > inp;
 
int ret;
int dp[NMAX][NMAX];
 
void sv(int a, int b) {
    if(dp[a][b] >= 0) return;
    else {
        int tCnt, tSum;
 
        tCnt = tSum = 0;
        for(int i=0;i<N;i++) {
            if(a >= inp[i].first.first or b >= inp[i].first.second) {
                tSum += inp[i].second;
                tCnt++;
            }
        }
 
        dp[a][b] = tCnt;
        ret = max( ret, dp[a][b] );
 
        // tSum: (1, 1)에서 (a, b)를 만들고 남은 경험치
        tSum -= (a-1) + (b-1);
 
        for(int nxtA=a;nxtA<=min( 1000, a+tSum);nxtA++) {
            int nxtB = min( 1000, b+(tSum-(nxtA-a)) );
 
            sv(nxtA, nxtB);
        }
    }
}
 
int main() {
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d %d %d", &a, &b, &c);
        inp.push_back({{a, b}, c});
    }
 
    memset(dp, -1, sizeof(dp));
    sv(1, 1);
 
    printf("%d", ret);
}
/*
5
1 1 1
1000 2 1
1333 3 1
2 112 1
4 112 112
ans: 4
 
3
1 1 1000
3 1000 1000
1000 2 1000
ans: 3
*/

후기

2차원 배열로 2가지 정보를 얻을 수 있는 재미있는 문제입니다. 재귀함수를 제외하고 별다른 기법도 필요없기에 동적 프로그래밍의 묘미를 느낄 수 있는 정말 좋은 문제라고 생각합니다. 물론 문제를 파악하는데 시간은 좀 걸렸지만 풀었을 때의 쾌감도 좋은 문제이기에 PS를 즐겨하는 사람들에게 꼭 추천하고 싶은 문제입니다.