BOJ 백준 20925번 메이플스토리

 

 

BOJ 백준 20925 메이플스토리

 

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

20925번: 메이플스토리

 

메이플스토리 게임에는 여러 사냥터가 있는데, 각 사냥터는 입장에 필요한 최소 경험치와 1분마다 얻는 경험치 값을 지닌다. 상원이는 T분 동안 N개의 모든 사냥터 중 하나 이상의 임의의 사냥터에서 경험치를 얻는다. 사냥을 시작하고 매 분마다 현재 사냥터에서 다른 사냥터로 갈지 결정할 수 있고, 한 사냥터에서 다른 사냥터로 이동하는 데는 시간이 든다. 상원이가 T분 동안 얻을 수 있는 경험치의 최댓값을 구하는 것이 문제이다.

 

 

전형적인 동적 프로그래밍(Dynamic Programming)으로 해결가능한 문제이다.

 

모든 N개의 사냥터에는 1번부터 n번까지 번호가 있다고 하자. 그리고 i번 사냥터 입장에 필요한 최소 경험치를 c[i], 1분마다 얻는 경험치를 e[i], i번 사냥터에서 j번 사냥터로 이동하여 입장하는 데까지 걸리는 시간을 t[i][j]라고 하자.

 

현재 위치한 사냥터가 n번 사냥터이고 그 때의 시간을 time이라고 할 때, 이 상황이 오기까지 얻을 수 있는 경험치의 최댓값을 d[time][n]이라고 하자. 이전 상황은 크게 두 가지로 나눌 수 있다. 하나의 경우는 1분 전에도 n번 사냥터에서 사냥을 하고 있는 상황이고, 다른 경우는 time - t[i][n] 시간까지 i번 사냥터에서 사냥을 하다가 t[i][n]만큼의 시간을 소요하여 n번 사냥터로 이동해 오는 것이다. 그런데 후자의 경우에는 n번 사냥터로 이동하기 전에 n번 사냥터 입장에 필요한 최소 경험치 이상이라는 조건을 만족해야 한다. 따라서 이를 종합하여 정리하면 다음과 같다.

 

 

X: 다른 사냥터에서 n번 사냥터로 이동해 오는 경우 중 누적 경험치의 최댓값

d[time][n] = max(X, d[time - 1][n] + e[n])

X = max(d[time - t[i][n]][i]) (단, i는 n을 제외한 다른 사냥터 번호, d[time - t[i][n]][i] >= c[n])

 

 

T분이 되기 전까지 매 분마다 1번부터 n번 사냥터까지 각각의 사냥터마다 1분 전에도 해당 사냥터에서 사냥을 한 경우와 다른 사냥터에서 시간을 소요하여 이동한 경우 중 가장 큰 값을 배열 d에 업데이트하는 방식으로 구현할 수 있다. 이 때의 시간 복잡도는 O(T*N²)인데, T의 최댓값은 1000이고 N의 최댓값은 200이므로 충분히 시간 내에 수행 가능하다.

 

 

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;


const int N_MAX = 200;
const int T_MAX = 1000;


int n, t;
int c[N_MAX], e[N_MAX];
int dp[T_MAX + 1][N_MAX];


int cost[N_MAX][N_MAX];


int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d %d", &n, &t);
    for (int i = 0; i < n; i++){
        scanf("%d %d", &c[i], &e[i]);
        if (c[i] == 0){
            dp[0][i] = 0;
        }
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &cost[i][j]);
        }
    }
    
    for (int i = 1; i <= t; i++){
        for (int j = 0; j < n; j++){
            if (dp[i - 1][j] != -1){
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + e[j]);
            }
            for (int k = 0; k < n; k++){
                int prev = i - cost[k][j];
                if (j == k || prev < 0) continue;
                
                if (dp[prev][k] != -1 && dp[prev][k] >= c[j]){
                    dp[i][j] = max(dp[i][j], dp[prev][k]);
                }
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= t; i++){
        for (int j = 0; j < n; j++){
            ans = max(ans, dp[i][j]);
        }
    }
    printf("%d\n", ans);
    
    return 0;
}