백준 20925번 메이플스토리

문제 요약

사냥터가 N개 주어진다. 각 사냥터에는 사냥터에 진입하기 위한 최소 경험치 $c_i$와 1분마다 얻는 경험치 $e_i$가 주어진다.

그리고 각 사냥터 간 이동에 필요한 시간도 주어진다.

총 $T$분을 쓸 수 있다고 할 때, 얻을 수 있는 최대경험치를 출력하시오.

사냥터의 개수 N은 최대 200이고, $T$는 최대 1000이다.

풀이

이리저리 생각해볼 수도 있지만 일단 dp를 생각하자.
$$
dp[i][j]=\text{i번째 사냥터에서 j분에 얻을 수 있는 최대 경험치}dp[i][j]=\text{i번째 사냥터에서 j분에 얻을 수 있는 최대 경험ㅊ}
$$
이러면 이제 j분에 i번째 사냥터에 있을 때 할 수 있는 선택은 두 종류가 있다. 이 사냥터에서 계속 사냥하거나, 다른 사냥터로 이동하거나.

이제 이를 전부 고려해서 dp테이블을 채워주면 된다. 계속 사냥한다면 $dp(i,j+1) = dp(i,j)+e_i$가 되고, 다른 사냥터 k로 이동한다면 $dp(i,j) \ge c_k$일 때만 가능하다.

#include<bits/stdc++.h>
using namespace std;
int dp[205][1005];
int N, T;
int c[205], e[205];
int t[205][205];

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    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 >> t[i][j];
    memset(dp, -1, sizeof(dp));
    for(int i=1;i<=N;++i) if(!c[i]) dp[i][0] = 0;
    for(int j=0;j<T;++j) {
        for(int i=1;i<=N;++i) {
            if(dp[i][j] == -1) continue;
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + e[i]);
            for(int k=1;k<=N;++k) {
                if(i == k) continue;
                int time = t[i][k];
                if(j+time > T) continue;
                if(c[k] > dp[i][j]) continue;
                dp[k][j+time] = max(dp[k][j+time], dp[i][j]);
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=N;++i) ans = max(ans, dp[i][T]);
    cout << ans << '\n';
    return 0;
}