백준- 퇴사(14501) - DP, DFS - Java

1. 문제

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

2-1. DP 풀이

DP가 가장 까다로운 부분 중에 하나가 어떠한 값을 DP로 잡을지에 관한 것이다.

여기서는 1일~N+1일째까지 상담을 하면서 가장 많은 이익을 낼 수 있는 가 이다.

이때 dp의 값은
dp[i] = i번째 날~N+1일째까지의 최대 이익
으로 생각할 수 있다.

따라서 이는 마지막 날부터 거꾸로 생각해보면 된다.

i = N-1로 두고
time = i + t[i]로 설정한다.

i = 7이라고 할때 time = 7 + 2 => 9가 된다.
문제가 N+1일째 퇴사 이기 때문에 만일 t[i]=1이라면 마지막 날도 상담을 할 수 있는 것이다.

3-1. 전체 코드

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());
        
        int tArr[] = new int[N];
        int pArr[] = new int[N];
        int dp[] = new int[N+1];
        
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int ti = Integer.parseInt(st.nextToken());
            int pi = Integer.parseInt(st.nextToken());
            
            tArr[i] = ti;
            pArr[i] = pi;
        }
        
        int maxValue = 0;
        
        for(int i = N - 1; i >= 0; i--){
            int time = i + tArr[i];
            if(time <= N){
                dp[i] = Math.max(pArr[i] + dp[time], maxValue);
                maxValue = dp[i];
            } else{
                dp[i] = maxValue;
            }
        }
        
        System.out.println(maxValue);
    }
}

---

2-2. DFS 풀이

DP가 N-1일차 부터 계산했다면, DFS는 편하게 1일차부터 생각하면 된다.

즉 i + T[i] <= N일때는 dfs(i + T[i], sum + P[i]) 로 하고 이때 maxValue를 sum+P[i]로 갱신해준다.

int time = i + Ti[i];
if(time <= N) {
	dfs(time, sum + Pi[i]);
	maxValue = Math.max(maxValue, sum + Pi[i]);
}

그 이후에는 1일차를 상담을 진행하지 않을 수도 있으니 그 다음날(i+1)일차부터 상담을 진행하는 것이다.

dfs(i+1, sum)

🚨주의 조건

dfs에는 반드시 i값의 종료 조건을 넣어줘야 한다. 그래야 ArrayOutOfBound 에러가 나지 않는다.

if(i >= N) {
	return;
}

2-3. DFS 코드

import java.util.*;
import java.io.*;
public class Main {

	static int maxValue;
	static int Ti[];
	static int Pi[];
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		Ti = new int[N];
		Pi = new int[N];
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			Ti[i] = Integer.parseInt(st.nextToken());
			Pi[i] = Integer.parseInt(st.nextToken());
		}
		
		maxValue = 0;
		dfs(0, 0);
		System.out.println(maxValue);
	}
	
	public static void dfs(int i, int sum) {
		
		if(i >= N) {
			return;
		}
		
		int time = i + Ti[i];
		if(time <= N) {
			dfs(time, sum + Pi[i]);
			maxValue = Math.max(maxValue, sum + Pi[i]);
		}
		dfs(i+1, sum);
		return;
	}

}