BOJ

문제

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

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

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

입력

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

다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마다 얻는 경험치 $e_i$가 주어진다. $(1≤c_i,e_i≤1000000)$

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

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

출력

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

풀이

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

• $T$분 동안 얻을 수 있는 최대 경험치를 구해야 합니다.
  
  

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

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

• 문제의 정답은 $dp(T, 1), dp(T, 2), …, dp(T, N)$ 중 가장 큰 값이 됩니다.
• 시간 복잡도 $O(T⋅N^2)$에 해결할 수 있습니다.
  • DP 상태가 $O(T⋅N)$개 존재합니다.
  • 각 상태마다 $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