[백준 20925번] 메이플스토리 (C++)

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

20925번: 메이플스토리

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, T, result = 0;
int c[200], e[200];
int t[200][200];
int dp[2000][1000]; 

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    memset(dp, -1, sizeof(dp));

    cin >> N >> T;
    
    for(int i=0; i<N; i++)
    {
        cin >> c[i] >> e[i];
        if(c[i]==0)
        {
            dp[i][0]=0;  //시작점
        }
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> t[i][j];
        }
    }

    for(int j=0; j<T; j++)      //시간 체크
    {
        for(int i=0; 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=0; k<N; k++)
            {
                if(j + t[i][k] > T) continue;  //현재 소요 시간 + 이동시간 체크
                if(c[k] > dp[i][j]) continue;  //입장 최소 경험치와 현재 경험치 체크
                dp[k][j + t[i][k]] = max(dp[k][j + t[i][k]], dp[i][j]);
            }
        }
    }

    for(int i=0; i<N; i++)
    {
        result = max(result, dp[i][T]);
    }

    cout << result;

    return 0;
}

dp에 누적하는 경우가 2가지이다.

먼저 최소 입장 경험치가 0일때부터 경험치 가성비가 더 좋은 사냥터를 발견하기 전까지 dp에 경험치를 누적시킨다.

 

경험치 가성비가 더 좋은 사냥터를 발견하면, 현재 누적된 시간 + 이동 시간을 고려하여 남은 시간 만큼 dp에 해당 사냥터의 경험치를 누적시킨다.

 

이후 dp에 해당 시간만큼 누적된 값중 가장 큰 값을 출력한다.