[알고리즘 - 백준] 14501번 퇴사(java)

백준 퇴사문제 링크

이 문제를 풀면서 조합으로 푸는 방법밖에 생각나지 않았다. 시간초과가 날까 싶었지만 일수(15일)이 작아서 DFS로 풀었다.

DFS 풀이방법

1. 현재 날짜(idx)라고 할때, 일이 마치는 날짜(idx + (arr[idx][0] -1))가 n일 안에 마치는 경우
   dfs(idx+arr[idx][0], sum+arr[idx][1]) 로, 첫번째 매개변수에는 일을 마친 그 다음날이 들어가고, 두번째 매개변수에는 비용이 들어간다.
2. n일 안에 마치지 못하는 경우
   dfs(idx+1, sum) 로, 첫번째 매개변수에는 다음날(idx+1)이 들어가고, 두번째 매개변수에는 원래의 비용(sum)이 그대로 들어간다.

DP 풀이방법

1. 마지막 날(n)부터 차례대로 1일이 될때까지 아래의 내용을 반복해준다.
   (1) nextDay에는 현재 날짜(i) + arr[i][0]의 합을 구한다.
   (2) nextDay-1 = "최종적으로 일을 마친 날짜" 라고 할때, nextDay-1가 n을 넘는다면 dp[i] = dp[i+1] 로 다음날짜의 dp를 물려준다.
   (3) (2)이 아니라면 즉, n을 넘지 않는다면 dp[i] = Math.max(dp[i+1], dp[nextDay]+arr[i][1]) 로 일을 하지 않는 경우(dp[i+1])와 일을 한 경우(dp[nextDay]+arr[i][1])의 dp값을 비교해 최댓값으로 갱신해준다.

import java.util.*;
import java.io.*;
class Solution{
	static int arr[][], n;
	static long dp[];
	static long maxSum, maxDpSum;
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		arr = new int[n+1][2];
		dp = new long[n+2];
		
		for(int i=1;i<n+1;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		dfs(1, 0);
		dp();
		
		for(int i=1;i<n+1;i++) {
			maxDpSum = Math.max(maxDpSum, dp[i]);
		}
		
		System.out.println(maxSum);
		System.out.println(maxDpSum);
		
	}
	public static void dfs(int idx, int sum) {
		maxSum = Math.max(maxSum, sum);
		if(idx > n) {
			return;
		}
		
		if(idx+(arr[idx][0]-1) <= n) {
			dfs(idx+arr[idx][0], sum+arr[idx][1]);
		}
		dfs(idx+1, sum);
		
	}
	public static void dp() {
		for(int i=n;i>=1;i--) {
			int nextDay = i+arr[i][0];
			if(nextDay-1>n) {
				dp[i] = dp[i+1];
			}else {
				dp[i] = Math.max(dp[i+1], dp[nextDay]+arr[i][1]);
			}
		}
	}
}