[Baekjoon Online Judge] 14501번: 퇴사
14501번: 퇴사
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
www.acmicpc.net
요구사항
- 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
- 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
- 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표가 입력으로 주어졌다고 가정한다.
| 1일 | 2일 | 3일 | 4일 | 5일 | 6일 | 7일 | |
| Ti | 3 | 5 | 1 | 1 | 2 | 4 | 2 |
| Pi | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
- 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
- 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
- 퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구한다.
입력
- 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
- 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
위 예시를 살펴보면, 6일 7일의 경우 T6, T7의 일수가 근무 할 수 있는 일수를 넘어서기 때문에 상담 일정을 잡을 수 없다. 최소한 5일에 잡혀있는 상담부터 진행 할 수 있다.
4일의 상담 소요 시간은 1일이다. 당일에 끝낼 수 있다. 4일과 5일을 진행하면 총 얻을 수 있는 수익은 20 + 15로 35이다.
3일의 상담 소요 시간은 1일이다. 당일에 끝낼 수 있다. 3일, 4일, 5일을 진행하며 총 얻을 수 있는 수익은 20 + 15 + 10으로 45이다.
2일의 상담 소요 시간은 5일이다. 즉 7일 부터 다시 상담이 가능하다. 7일은 소요 시간이 2일이기 때문에 상담을 진행 할 수 없다. 결국 얻을 수 있는 수익은 0 + 20으로 20이 된다. 이렇게 되면 차라리 상담을 진행하지 않고 3, 4, 5일을 진행하는 수익이 더 높게 된다.
1일의 상담 소요 시간은 3일이다. 즉 4일 부터 다시 상담이 가능하다. 4일 부터 얻을 수 있는 수익은 위에서 구했던 대로 35이다. 1일의 수익은 10이다. 35 + 10은 45의 수익을 얻을 수 있다.
결국 1일 4일 5일 상담일은 하면 45의 수익을 얻을 수 있고, 3일 4일 5일 상담을 해도 45의 수익을 얻을 수 있다. 이것을 dp 테이블에 정리하였다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| dp | 45 | 45 | 45 | 35 | 15 | 0 | 0 |
중점적으로 살펴볼 부분은 상담을 안할 수도 있다는 것이다. 상담을 안하면 이전까지 받을 수 있는 가장 최고의 수익을 유지할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Baekjoon14501 {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
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++) {
String[] input = bufferedReader.readLine().split(" ");
t[i] = Integer.parseInt(input[0]);
p[i] = Integer.parseInt(input[1]);
}
for (int i = n; i > 0; i--) {
// 상담을 할 수 있는지 판별하기 위해 상담을 시작 할 수 있는 day를 구한다.
int day = i + t[i];
// 입력받은 day가 상담할 수 있는 날보다 크게되면 상담을 할 수 없으므로 이전 수익을 유지한다.
if (day > n + 1) dp[i] = dp[i + 1];
// 상담이 가능하면, 이전 수익과 오늘 얻을 수 있는 수익 + day까지 얻을 수 있는 수익을 비교한다.
else dp[i] = Math.max(dp[i + 1], p[i] + dp[day]);
}
System.out.println(dp[1]);
bufferedReader.close();
}
}DFS를 활용한 풀이
다이나믹 프로그래밍이 아닌 DFS를 활용한 방식으로 풀이를 찾아보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Baekjoon14501 {
private static int n, answer = 0;
private static int[] t, p;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bufferedReader.readLine());
t = new int[n + 1];
p = new int[n + 1];
for (int i = 1; i <= n; i++) {
String[] input = bufferedReader.readLine().split(" ");
t[i] = Integer.parseInt(input[0]);
p[i] = Integer.parseInt(input[1]);
}
dfs(1, 0);
System.out.println(answer);
}
private static void dfs(int day, int value) {
// day 가 n + 1 이상이 되면 퇴사를 진행한다.
if (day >= n + 1) {
answer = Math.max(answer, value);
return;
}
// today 에 상담을 하는 경우 다음 상담 day 는 n + 1 day 를 넘을 수 없다.
if (day + t[day] <= n + 1) dfs(day + t[day], value + p[day]);
// today 에 상담을 하지 않는 경우 다음날로 넘어간다.
if (day + 1 <= n + 1) dfs(day + 1, value);
}
}
상담을 할 때와 안할 때를 기준으로 깊은 탐색을 진행한다. day가 n + 1이 되면 퇴사를 진행하기 때문에 적절하게 return하여 처리해준다.
DFS 관련해서는 아직 확실하게 와닿는 느낌이 없어서 지속적으로 DFS에 대한 공부를 해야 할 것 같다.