[BOJ 15486] 퇴사2

[BOJ 15486] 퇴사2

 

1. 문제 : Link

최대 수익 비교

 

2. 풀이

Math.max(max, dp[i]) 해주는 이유 -> 이전까지의 max값과 지금 현재 dp 값 중 최대값을 해당 지점에 더해주기 위해

(

 

3. 코드

import java.io.IOException;
import java.util.*;

public class Main {
    static int[] t;
    static int[] p;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        t = new int[n + 2];
        p = new int[n + 2];
        dp = new int[n + 2];

        for (int i = 1; i <= n; i++) {
            t[i] = sc.nextInt();
            p[i] = sc.nextInt();
        }

        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n + 1; i++) {
            max = Math.max(max, dp[i]);

            if (i + t[i] < n + 2 && (max + p[i] > dp[i + t[i]])) {
                dp[i + t[i]] = max + p[i];
            }
        }
        System.out.println(max);
    }
}