[백준][JAVA] 14501 : 퇴사

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

14501번: 퇴사

dp 또는 dfs로 해결 가능한 문제이며 아래 해답 코드는 dp를 사용하였다.

 

< 주요 for 문 >

1. 편의를 위해 마지막 날부터 거꾸로 계산한다.

2. nowTime = 현재 날짜 + 상담에 걸리는 일 수

3. nowTime이 N+1보다 크면 dp[i]는 dp[i+1]과 동일

      N+1 → 마지막 날(N번 째 날) 상담에 걸리는 일 수가 하루일 경우를 대비

4 - 1. 현재 날짜 i일의 상담을 선택하지 않은 경우 →  dp[i+1]
4 - 2. 현재 날짜 i일의 상담을 선택한 경우 이익 →  p[i] + dp[nowTime]

      →  현재 날짜의 상담을 통한 이익 : p[i] 

      →  현재 날짜의 상담을 끝낸 날에 대한 이익의 최댓값 : dp[nowTime]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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;
        int N = Integer.parseInt(br.readLine());
        int[] T= new int[N+2]; 
        int[] P = new int[N+2];
        int[] dp = new int[N+2];

        for(int i = 1; i<=N; i++) {
            st = new StringTokenizer(br.readLine()," ");
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = N; i > 0; i--) {
            int nowTime = i+T[i]; 
            if(nowTime > N+1) dp[i] = dp[i+1];
            else dp[i] = Math.max(dp[i+1], P[i]+dp[nowTime]);
        }
        System.out.println(dp[1]);
    }
}