BOJ - 퇴사

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

---

Problem

---

Solve

해당 문제는 브루트포스로 풀 수 있고, DP로도 풀 수 있는 문제입니다.
기억은 안나지만 전에 브루트포스로 풀은 경험이 있길래 DP로 풀어보겠습니다.
(점화식을 못구해서 다른 분의 코드를 참조하였습니다.)

T[i]에는 현재 날짜에서 상담이 걸리는 시간
P[i]에는 현재 날짜에 상담을 시작하면 얻는 비용
DP에는 해당 날짜에 얻을 수 있는 가장 큰 금액이 저장됩니다.
DP에는 현재 날짜에서 상담을 시작하고 상담이 끝나는 날 이후에 상담했을때의 가장 큰 금액과 현재 날짜에 상담하지 않았을때 가장 큰 금액을 비교해서 갱신합니다.
즉, DP[i] = Math.max(DP[i+T[i]] + P[i] , DP[i+1])

DP[i+T[i]]은 현재 날짜에 상담을 시작하고 다음 상담을 수행할 수 있는 날짜의 최대 금액입니다.
현재 날짜에 상담을 시작했으니 P[i]를 합하여 비교해주어야합니다.
현재 날짜에서 상담이 가능할 날짜의 DP를 구해야하기 때문에 DP의 앞에서가 아닌 뒤에서 부터 시작합니다.

DP[i+1]은 현재 날짜에 상담을 받지 않는 경우로, DP를 뒤에서 부터 비교하기 때문에 현재 날짜의 뒤의 DP와 비교해야합니다.

그리고 현재 날짜에서 상담을 시작했을때 퇴사하는 날을 넘어간다면 그 날짜에는 상담을 할 수 없기때문에 해당 날짜 이후의 날을 DP에 저장해야합니다.

if(i+T[i] > N+1) DP[i] = DP[i+1];

이를 반복하면 DP[1]의 값에 최대 금액이 저장되어 있게됩니다.

---

Code

import java.io.*;
import java.util.StringTokenizer;
public class 퇴사{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		}
        //DP에 크기 1을 더 늘려 DP[N]에서 DP[N+1]의 값을 비교할 수 있도록 해줍니다.
		int[] dp = new int[N+2];

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

		bw.write(String.valueOf(dp[1]));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://waristo.tistory.com/13