문제

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

풀이

백트래킹(DFS) 풀이

• DFS 를 사용하여 해결한다.
  • 탈출 조건: 날짜(idx)가 N 이상이면 result 중 최댓값을 구하며 끝낸다.
  • 만약 상담을 끝낸 날이 N 이하라면. 즉, idx + schedule[idx][0] <= N 라면 dfs에 상담이 끝난 날짜와 합친 상담비를 넣는다.
  • 만약 상담을 끝낸 날이 N 을 넘어간다면. 즉, 상담을 퇴사날까지 끝마칠 수 없다면 dfs에 상담이 끝난 날짜만 넘겨준다. -> 합친 상담비는 그대로고 넘겨준 날짜는 탈출 조건에서 사용한다.
  • dfs(idx + 1, pay) 를 dfs 끝에 넣어주어 이어서 상담하지 않고 날짜를 띄워서 새로운 날짜를 탐색할 수 있도록 해준다. -> 마지막 날짜까지 모두 탐색해볼 수 있다.

백트래킹(DFS) 코드

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

public class Main {

	static int N;
	static int[][] schedule;
	static int result;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine()); // N까지만 일 함
		schedule = new int[N][2];
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			schedule[i][0] = Integer.parseInt(st.nextToken()); // 상담 하는데 걸리는 일 수
			schedule[i][1] = Integer.parseInt(st.nextToken()); // 돈
		}
		
		result = 0;
		// 0일 부터 시작함
		dfs(0, 0);
		
		System.out.println(result);
	}
	
	static void dfs(int idx, int pay) {
		if(idx >= N) {
			result = Math.max(pay, result);
			return;
		}
		
		if(idx + schedule[idx][0] <= N) { // 상담을 끝마칠 수 있다면 -> 상담이 끝난 날짜와 상담비 넣음
			dfs(idx + schedule[idx][0], pay + schedule[idx][1]);
		} else { // 상담을 끝마칠 수 없다면 -> 상담이 끝난 날짜만 넘겨준다(탈출 조건으로 써먹음)
			dfs(idx + schedule[idx][0], pay);
		}
		
		// 이어서 상담하지 않고 날짜를 띄워서 새로운 날짜를 입력 (0일부터 마지막 날짜까지 다 훑을 수 있음)
		dfs(idx + 1, pay);
	}
	
}

DP 풀이

• 날짜의 끝 부터 첫 날 까지 거꾸로 DP 배열을 구해나간다.
• 배열 DP[i]는 날짜 i 부터 상담을 했을 때 벌 수 있는 돈의 최댓값이다.
  • 예를 들어 DP[5] 라면 5일 부터 일 한 값 중 최댓값이다.
  • 그러므로 DP[1] 을 구해주면 된다.
• i + T[i] > N + 1 라면 i 날짜에는 일을 할 수 없다.
  • 따라서 DP[i] 의 값은 DP[i + 1] 이 된다.
  • i의 날짜에 i의 일을 하지 못한다면 i + 1 의 날짜부터 일해서 번 돈의 최댓값과 i 의 날짜부터 일해서 번 돈의 최댓값이 같기 때문이다.
• i + T[i] <= N + 1 라면 i 날짜에 일을 할 수 있다.
  • 일을 하지 않았을 때의 값 DP[i + 1]
  • i 날짜의 일을 하면 i 날짜의 페이인 P[i] 와 i 날짜 이후에 번 돈의 최댓값인 DP[i+T[i]] 의 합인 값 P[i] + DP[i+T[i]]
  • 위의 DP[i + 1] 과 P[i] + DP[i+T[i]] 값 중 더 큰 값을 DP[i]에 넣어준다.

DP 코드

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]);
	}

}

정리

• DFS 와 DP 모두 공부할 수 있는 문제였다.
• DP를 사용할 때 뒤에서부터 시작하는 것도 좋은 방법이다.