백준 14501 - 퇴사

Java

14501 번 - 퇴사

문제

1일부터 N일까지 매일 [상담을 완료하는데 걸리는 기간 T], [받을 수 있는 금액 P]이 주어진다.
각 상담을 완료한 기간이 N + 1을 넘지 않을때 해당 상담을 할 수 있고 해당하는 금액을 받는다.
최대 수익을 구하라

접근 방법 1 - DFS

n개의 상담을 어떻게 선택하는 가에 따라 이익이 달라지므로, n개의 각 일에 해당된 상담을 [선택하는지 선택하지 않는지]에 따라 나누어 부분집합으로 해결하였다.

코드

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

public class Main {
	static int n, result;
	static int[] T, P;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	T = new int[n + 1];
    	P = new int[n + 1];
    	
    	for(int i = 1; i <= n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		T[i] = stoi(stk.nextToken());
    		P[i] = stoi(stk.nextToken());
    	}
    	Work(1,0);
    	System.out.println(result);
    	br.close();
	}

	static public void Work(int d, int sum) {
		// 현재 상담을 선택하고, 해당 상담을 완수 하였을 때 n + 1 이전인 경우
		if(d + T[d] < n + 1) {
			Work(d + T[d], sum + P[d]);
		}
		// 현재 상담 날짜를 선택하지 않는 경우
		if(d + 1 < n + 1)
			Work(d + 1, sum);
		
		// 현재 상담을 이수하면 마지막 일인 경우
		if(d + T[d] == n + 1) {
			result = Math.max(sum + P[d], result);
		}
		
		
		result = Math.max(sum, result);
		return;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

접근 방법 2 - DP

DP로도 해결하였다.
각 날 마다 상담을 진행하였을때, 끝나는 날의 이익이 크다면 계속하여 갱신한다.

1일의 상담 기간은 3이고 현재 이익은 0이므로, 1 + 3을 하여 4일의 이익을 10으로 갱신
2일의 상담 기간은 5이고 현재 이익은 0이므로, 2 + 5를 하여 7일에 이익을 20으로 갱신
3일의 상담 기간은 1이고 현재 이익은 0이므로, 3 + 1를 하여 4일에 이익을 10이며, 현재 4일의 이익은 10으로 똑같으므로 갱신하지 않는다.
4일의 상담 기간은 1이고 현재 이익은 20이므로 , 4 + 1를 하여 5일에 이익을 30으로 갱신
5일의 상담 기간은 2이고 현재 이익은 30이므로 , 4 + 1를 하여 7일에 이익을 43으로 갱신 6일과 7일은 상담기간이 각각 4,2일 이므로 7일을 초과한다 따라서 상담을 할 수 없다.

코드

int[] dp = new int[n + 2];
for(int i = 1; i <= n; i++) {
	// 현재 날짜까지의 최대 이익을 가져온다.
	dp[i] = Math.max(dp[i], dp[i-1]);
	// 현재 날짜와 상담일을 더한 날의 최대 이익으로 갱신한다.
	if(T[i] + i < n + 2)
		dp[T[i] + i] = Math.max(P[i] + dp[i], dp[T[i] + i]);
}

for(int i = 1; i <= n + 1; i++) {
	result = Math.max(result, dp[i]);
}

총평

난이도

⭐⭐★★★

후기

이전에 풀었던 문제이다.
이번에는 이전과 다르게 dfs를 통하여 풀었으며, 이전에 dp로 푼 기록이 남아 다시 dp로 풀어보았다.

개선할 점

dp를 알쟈