[백준] 1315번 RPG

1315 RPG

문제

---

준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다.

게임에는 총 N개의 퀘스트가 있다. i번째 퀘스트를 깨려면 캐릭터의 힘이 STR[i]보다 크거나 같거나, 지력이 INT[i]보다 크거나 같아야 한다. 이 퀘스트를 깨면, 스탯을 올릴 수 있는 포인트를 PNT[i]개 만큼 얻게 된다.

모든 퀘스트는 단 한 번만 깰 수 있으며, 퀘스트를 깨는 순서는 준규가 마음대로 정할 수 있다. 또, 퀘스트 보상으로 얻게되는 포인트로 준규 마음대로 스탯을 올릴 수 있다.

준규가 깰 수 있는 퀘스트 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 퀘스트의 개수 N이 주어진다. N은 100보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 STR[i], INT[i], PNT[i]가 주어진다. 이 숫자는 모두 1,000보다 작거나 같은 자연수이다.

출력

---

첫째 줄에 준규가 깰 수 있는 퀘스트 개수의 최댓값을 출력한다.

---

풀이)

다른 분들의 코드 도움을 받아 푼 문제이다.

다이나믹 프로그래밍이긴 하나 재귀도 사용해야 하는 문제였다.

재귀까지 사용해본 적이 없어서 어려움을 겪었다.

점화식을

dp[i][j] = 힘 스탯이 i, 지력 스탯이 j일때 깰 수 있는 퀘스트 개수의 최대값 이라고 할 때,

풀이법은 이러하다.

1. 현재 스탯으로 깰 수 있는 퀘스트들의 포인트를 더한다.

2. 구한 포인트들로 힘과 지력에 나눠지는 모든 경우의 수를 다 확인한다. (이때 재귀사용)

3. 각 경우에서 깰 수 있는 퀘스트의 최대값을 구한다.

위의 과정(1~3)을 반복하는 함수를 만들어서 풀었다.

설명하기가 어려워 코드를 보고 학습하는 것이 더 쉬울 것 같다.

코드)

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
 
int n;
int q[100][3]; //퀘스트 저장
int dp[1001][1001]; //dp[i][j] = 능력치각 각각 i,j일때 최대 퀘스트 수행 개수
bool visited[100];//했던 퀘스트인지 확인하는 변수
 
int cal(int a, int b) { //힘이 a, 지력이 b일 때 퀘스트 몇개 할 수 있는지 구하는 함수
 
    //이미 이전에 계산했던 값이라면
    if (dp[a][b] != -1) return dp[a][b];
 
    int point = 0;
    dp[a][b] = 0;
    vector <int> check;
    for (int i = 0; i < n; i++) {
        if (q[i][0] <= a || q[i][1] <= b) {
            dp[a][b] += 1;
            //함수에 함수를 타고 와서,이전에 했던 퀘스트면 pass
            if (visited[i]) continue;
 
            point += q[i][2];
            visited[i] = true;
            check.push_back(i);
        }
    }
 
    for (int i = 0; i <= point; i++) {
        //능력치는 1000을 넘으면 안됨
        dp[a][b] = max(dp[a][b], cal(min(1000, a + i), min(1000, b + (point - i))));
    }
 
    //a,b일때 했던 퀘스트 다시 원상복귀, 이전상태에서 다른 능력치일때를 봐야하므로
    for (int i = 0; i < check.size(); i++) {
        visited[check[i]] = false;
    }
 
    return dp[a][b];
}
 
int main() {
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        //퀘스트의 STR, INT, PNT
        scanf("%d %d %d", &q[i][0], &q[i][1], &q[i][2]);
    }
    memset(dp, -1, sizeof(dp));
    printf("%d", cal(1,1));
    return 0;
}