백준 14501번 : 퇴사

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

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

public class Main {
    int n;
    int[] dp;
    int[] t;
    int[] p;
    int max = 0;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        t = new int[n];
        p = new int[n];
        dp = new int[n+1];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=0; i<n; i++){
            if(i+t[i]<=n){
                dp[t[i]+i] = Math.max(dp[t[i]+i], dp[i]+p[i]);
            }
            dp[i+1] = Math.max(dp[i+1], dp[i]);
        }
        System.out.println(dp[n]);
    }



    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

예전에 완전탐색으로 풀었던 문제였지만, DP로 다시 풀었다.

혼자 풀어보다가 왜맞왜틀 반복하다가 다른 사람의 블로그를 참고 했다.

(https://hidelookit.tistory.com/118)

i+t[i]가 n보다 작아서 일을 할 수 있는 경우 그 날짜에 보수를 저장하고, 그 날짜까지 저장된 보수와 새로운 일을

맡았을 경우의 보수를 비교해서 더 큰 값을 저장한다.

 

해당 날짜가 0 일 경우를 대비해 그 전까지 저장되어 있던 최대 값을 저장해주는 코드를 추가해준다.