퇴사 [백준 14501][실버4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

14501번: 퇴사

DFS 문제.

1. Work 배열에 work들을 담는다.

2. 0번째부터 N번째 까지 DFS를 시작한다.

3. 자신의 상담시간 + 자신의 현재 day보다 높은 번째의 상담일까지 DFS를 돈다.

4. 자신의 상담시간 + 자신의 현재day가 N을 넘기면 return한다.

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

class Work{
	int day, reward;
	public Work(int day , int reward){
		this.day = day;
		this.reward = reward;
	}
}
public class Main {
	static Work[] work;
	static int N;
	static boolean visit[];
	static int max = Integer.MIN_VALUE;
	public static void main(String[] args) throws Exception {
		Scanner sc= new Scanner(System.in);
		
		N = sc.nextInt();
		visit = new boolean[N];
		work = new Work[N];
		for (int i = 0; i < N; i++) {
			work[i] = new Work(sc.nextInt(), sc.nextInt());
		}
		
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			max = Math.max(dfs(i,0),max);
		}
		System.out.println(max);
	}
	public static int dfs(int cur, int reward) {
		if(cur + work[cur].day == N) {
			return reward + work[cur].reward;
		}
		else if(cur + work[cur].day > N) {
			return reward;
		}
		
		for (int i = 0; i < N; i++) {
			//자신이거나 자신 이하의 상담이면 x
			if(cur >= i) continue;
			//현재 상담 시간 이하면 x
			if(cur + work[cur].day > i) continue;
			//N을 넘기면 x
			if(cur + work[cur].day >= N) {
				continue;
			}
			
			max = Math.max(dfs(i , reward + work[cur].reward), max);
		}
		
		return max;
	}
}