[백준 14501] 퇴사 / 자바 / dp(기본)

문제         

레벨:  S3
알고리즘: dp(기본)
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도   

[알고리즘 설명]

위 문제는 dp의 대표문제인 배낭문제(Knapsack Problem)와는 다르다. 배낭문제는 앞에 가방을 선택하더라도 무게 여유가 있다면 선택할 수 있지만, 위 문제는 앞에 이틀짜리 스케줄을 선택한다면 뒤에 스케줄을 선택을 못한다. 
위 dp 문제는 일반적인 최소한의 일수로 최대치값을 구하는 문제와 다르다는 인지하고 들어가야 한다. 주어진 일수와 탐색 색 스케줄 두개를 기준으로 dp를 업데이트 해가는 것이 아닌 주어진 일수, 탐색 스케줄을 한 번에 묶어서 기준 한 개로 탐색해야 한다. (새로운 유형)

그래서 dp의 인덱스 0에서부터 채우는 것이 아닌 N에서부터 0으로 탐색하는 것도 특이점 중 하나이다.
헷갈리지 마시오.

dp[i]는 i일까지의 최대치가 아니라 i부터 N일 까지의 최대치이다. 이렇게 하는 이유는 기존 dp방식으로 한다면 dp[N]의 값이 dp[N-1]의 값의 영향을 미칠 수 있기 때문이다. 예를 들면, 6일차까지 탐색했을 때 5일의 스케쥴을 받는 게 최대치였다면 7일차를 탐색했을 때 5일차의 스케줄을 예약을 안해야 7일차를 할 수 있다. 7일차가 극단적으로 값(V)이 크다면 5일차를 안 하고 7일차를 하는 것이 맞다. 그렇다면 dp이전 값은 쓸모없어지는 것이다. dp란 전의 값을 참조해서 채워가는 방식인데 이전 방식이 쓸데없어진다? 이러한 사고의 틈을 메꾸기 위해 거꾸로 채워가는 것이다. 

base case 부터 시작해서 답을 업데이트 해가는 방식이므로 아래 방식은 bottom-up 방식이다.

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); // N까지만 일 함
		
		int[] T = new int[N+1];
		int[] P = new int[N+1];
		int[] DP = new int[N+2];
		
		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()); // 돈
		}
		
		for(int i = N; i > 0; i--) {
			int next = i + T[i]; // 현 인덱스 스케줄을 소화한 후의 날짜
			
			if(next > N + 1) { // 일할 수 있는 날짜를 넘어가는 경우
				// 일을 하지 못하는 스케줄이므로 이전 탐색 dp값으로 설정
				DP[i] = DP[i + 1];
			} else { // 스케줄을 소화할 수 있는 경우
				// 1. 현 인덱스 스케줄을 잡지 않았을 때(DP[i + 1])
				// 2. 현 인덱스 스케줄을 잡았을 때(P[i] + DP[next])
				// 위 두 경우 중 더 큰 값을 DP에 넣어준다.
				DP[i] = Math.max(DP[i + 1], P[i] + DP[next]);
			}
		}
		
		System.out.println(DP[1]);
	}

}

동작 과정 

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50