BOJ 20925번: 메이플스토리

2021-02-23

BOJ

문제

상원이는 겨울방학 동안 메이플스토리를 할 것이다. 개강 후에는 바쁘기 때문에 방학 동안 최대한 레벨을 많이 올리려고 한다.

서강대컴공

메이플스토리에는 여러 가지 사냥터가 있다. 각 사냥터는 입장에 필요한 최소 레벨, 지형, 몬스터 레벨, 몬스터 수, 버닝 등등 다양한 특징을 가진다. 상원이는 경험치가 가장 중요하기 때문에 사냥터의 특징을 입장에 필요한 최소 경험치1분마다 얻는 경험치로 간략화했다. 사냥을 시작하고 매 분마다 지금 있는 사냥터에서 계속 사냥할지 다른 사냥터로 갈지 결정한다. 코디 아이템에 돈을 다 써 텔레포트를 할 수 없는 상원이는 사냥터 사이를 직접 걸어서 이동한다. 사냥터 사이를 이동하는 동안 사냥을 할 수 없기 때문에 경험치를 얻을 수 없다.

처음에 캐릭터의 경험치는 0이기 때문에 입장에 필요한 최소 경험치0인 사냥터 중 하나를 골라 사냥을 시작한다. 상원이가 방학 동안 얻을 수 있는 경험치의 최댓값을 알려주자.

입력

첫째 줄 사냥터 수 N (1N200)과 방학 기간을 분 단위로 나타낸 T (1T1000)가 주어진다.

다음 N개의 줄에는 i번째 사냥터의 특징인 입장에 필요한 최소 경험치 ci1분마다 얻는 경험치 ei가 주어진다. (1ci,ei1000000)

다음 N개의 줄에는 각 사냥터 사이를 이동하는 데 걸리는 시간이 주어진다. i번째 줄의 j번째 수는 i번 사냥터에서 j번 사냥터로 이동하여 입장하는 데까지 걸리는 시간을 분 단위로 나타낸 값 ti,j이다. (1ti,j1000,ti,j=tj,i,ti,i=0)

단, 입장에 필요한 최소 경험치 ci0인 사냥터는 반드시 하나 이상 존재한다.

출력

상원이가 방학 동안 얻을 수 있는 경험치의 최댓값을 출력한다.

풀이

  • 입장에 필요한 최소 경험치가 0인 사냥터중 하나에서 사냥을 시작합니다.
  • 현재 경험치보다 입장에 필요한 최소 경험치가 낮거나 같은 사냥터로 이동할 수 있습니다.
  • 사냥을 시작하고 매 분마다 다른 사냥터로 이동할지 말지 결정합니다.
  • T분 동안 얻을 수 있는 최대 경험치를 구해야 합니다.

  • 이 문제는 Dynamic Programming으로 해결할 수 있습니다.
    • dp(i,j):=i초간 사냥하고 j번 사냥터에서 사냥이 끝날때 얻을 수 있는 최대 경험치

  1. dp(i,j)cj를 만족하는 사냥터에 대해 다음과 같이 행동할 수 있습니다.
    • 사냥터를 옮기지 않고 계속 사냥하는 경우, dp(i+1,j)를 업데이트 할 수 있습니다.
  2. dp(i,j)ck를 만족하는 사냥터에 대해 다음과 같이 전이할 수 있습니다.
    • k번 사냥터로 옮기기로 한 경우, dp(i+t[j][k],k)를 업데이트 할 수 있습니다.

  • 문제의 정답은 dp(T,1),dp(T,2),,dp(T,N) 중 가장 큰 값이 됩니다.
  • 시간 복잡도 O(TN2)에 해결할 수 있습니다.
    • DP 상태가 O(TN)개 존재합니다.
    • 각 상태마다 O(N)개의 상태로 전이합니다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int c[201], e[201];
int matrix[1001][1001];
int dp[1001][201];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t; cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> c[i] >> e[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> matrix[i][j];
        }
    }
    for (int i = 0; i < t; i++) {
        for (int j = 1; j <= n; j++) {
            // 사냥터를 옮기지 않고 계속 사냥하는 경우
            if (dp[i][j] >= c[j]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + e[j]);
            for (int k = 1; k <= n; k++) {
                if (i + matrix[j][k] <= t && dp[i][j] >= c[k]) {
                    // k번 사냥터로 옮기기로 한 경우
                    dp[i + matrix[j][k]][k] = max(dp[i + matrix[j][k]][k], dp[i][j]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[t][i]);
    cout << ans << "\n";
    return 0;
}

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