[JAVA] 백준 14501번 : 퇴사 (삼성 SW 역량 테스트 기출 문제)

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

문제

나는 DFS로 풀었다. 풀고나서 다른 사람들의 풀이를 보니 DP를 이용하여 푼 것을 확인하였다.
다음 복습에는 꼭 DP로 풀어봐야겠다.

 

해결 방안

1부터 N일 까지 상담이 가능하며 하루에 1개씩만 상담이 가능하다. 이 부분에서 걸리는 시간 비교를 통한 DFS를 이용하면 구할 수 있을 것이라고 생각하였다. 

1. DFS 탐색 시작 부분에서 반복문을 이용해서 1~N일까지 DFS 탐색을 하는데 i + T[i] 가 N+1이 넘어가는 순간은 제외하고 진행하였다. (문제에서 퇴직날까지 상담이 가능하다고 하였므르로)

2. 그리고 DFS 탐색 부분에서 기저 사례는 dfs 함수에서 보내준 index 값과 T[index]의 합이 N+1이 넘어가는 순간이다.
그 순간 최대값을 계속 갱신해준다.

3. 그외 DFS 탐색 부분에서는 dfs 함수에서 보내준 index 값에 T[index] 더한 수 부터 다시 DFS 탐색을 해준다.
이 때 기저사례로 빠질 수 있는 조건을 만들어준다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 퇴사
// N+1일 째 되는 날 퇴사
// 남은 N일 동안 최대한 많은 상담
// 하루에 상담 1개만 가능
public class Main {
	
	static int N; // 상담 가능 일수
	static int[] T; // 상담을 완료하는데 걸리는 시간
	static int[] P; // 상담을 했을 때 받을 수 있는 금액
	
	static int result = 0; // 최대 이익

	public static void main(String[] args) throws Exception, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		T = new int[N+1];
		P = new int[N+1];
		
		String str;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			T[i] = Integer.parseInt(str.split(" ")[0]);
			P[i] = Integer.parseInt(str.split(" ")[1]);
		}
		
		int sum = 0;
		for(int i=1; i<N+1; i++) {
			sum = 0;
			if(i+T[i]<=N+1) {
				sum = P[i];
				dfs(i, sum);
			}
		}
		
		System.out.println(result);

	}
	
	public static void dfs(int index, int sum) {
		if(index + T[index] >= N+1) {
			result = Math.max(result, sum);
		}
		else {
			for(int i = index+T[index]; i<N+1; i++) {
				if(i+T[i]<=N+1) {
					sum += P[i];
					dfs(i, sum);
					sum -= P[i];
				}
				else {
					dfs(i, sum);
				}
			}
		}
	}

}