[백준] 20925번 - 메이플스토리 (Java)

문제

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

20925번: 메이플스토리

 

입력

 

 

출력

---

알고리즘

다이나믹 프로그래밍

 

각 초마다 다른 곳으로 이동할지 아니면 계속 현재 사냥터에서 사냥하는게 더 유리할지 따져보고 dp 테이블을 갱신하면 된다.

이때, 각 던전별 입장 제한 경험치가 있으므로 사냥터를 이동할때는 이를 만족하는지 확인해줘야 한다. 또한, 던전과 던전을 이동할 때 이동 시간이 있으므로 시간내에 이동할 수 있는지 확인해줘야한다. 이렇게 각초마다 각 던전에서 사냥을 마무리 했을때 얻을 수 있는 경험치 최댓값을 기록해두고, 마지막에 이 중에서 제일 큰 것을 출력하면 된다.

 

dp[i][j] : i초까지 사냥을 했고, j번째 던전에서 사냥을 마쳤을때 얻을 수 있는 경험치의 최댓값. dp[i][j]가 될 수 있는 것은 제자리에서 계속 사냥하는 경우인 dp[i-1][j]와 다른 던전에서 넘어오는 경우인 dp[prev][k] 둘중 하나임.

 

dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + dungeon[j][1]) : 현재 사냥터에서 계속 사냥할지 말지 고민하는 것. 이때도 역시 현재 경험치가 던전 입장 최소 경험치를 만족해야 사냥이 가능하므로 이 조건을 넣어줘야 함.

 

prev = i - move[k][j] : move[k][j]는 k번째 던전에서 j번째 던전으로 이동하는데 걸리는 시간, 따라서 prev는 j 던전으로 오기 전의 시간을 의미함. 이 값이 음수이면 제시간내에 도달이 불가능 함.

dp[i][j] = Math.max(dp[prev][k], dp[i][j]) : k던전에서 j던전으로 이동할 경우

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        //던전별 최소경험치와 분당 얻는 경험치
        int[][] dungeon = new int[n][2];

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            dungeon[i][0] = Integer.parseInt(st.nextToken());
            dungeon[i][1] = Integer.parseInt(st.nextToken());
        }

        //각 던전별 이동 시간
        int[][] move = new int[n][n];
        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<n; j++){
                move[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //dp[i][j] : i초까지 사냥했고 j번째에서 사냥을 끝마쳤을때 경험치 최댓값
        int[][] dp = new int[t+1][n];

        for(int i = 1; i<=t; i++){
            for(int j = 0; j<n; j++){
                //던전을 이동하지 않고 제자리 사냥 (이때, 현재 경험치가 제한 조건을 만족해야됨)
                if(dp[i-1][j] >= dungeon[j][0]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + dungeon[j][1]);
                for(int k = 0; k<n; k++){
                    //던전을 이동해서 온 경우 (k던전에서 j로 이동)
                    int prev = i - move[k][j]; //j로 오기전, k에서의 시간
                    if(j == k || prev<0) continue; //현재 시간으로 못오거나 이전꺼랑 같은거면 무시
                    //j던전에 입장하기 위한 충분한 경험치를 소지하고 있을 경우에만 최댓값 갱신
                    if(dp[prev][k] >= dungeon[j][0])dp[i][j] = Math.max(dp[prev][k], dp[i][j]);
                }
            }
        }

        //방학이 끝나는 시점에서 어느 던전에서 마무리한게 가장 최대의 경험치인가?
        int max = 0;
        for(int i = 0; i<n; i++){
            max = Math.max(max, dp[t][i]);
        }

        System.out.println(max);
    }

}