접근
처음에는 앞에서부터 값을 결정하려고 해봤다.
현재 날짜를 기준으로 상담에 소요되는 시간을 고려해서 끝나는 날짜의 값을 최대 수익이 되도록 갱신하는 방향으로 작성해봤다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N 입력 받기
int N = Integer.parseInt(br.readLine());
// 금액 입력 받기
int[] time = new int[N];
int[] fee = new int[N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
fee[i] = Integer.parseInt(st.nextToken());
}
// dp
int[] dp = new int[N];
for (int i = 0; i < N; i++) {
int t = time[i] - 1;
if (i + t < N) {
dp[i + t] = Math.max(dp[i + t], dp[i] + fee[i]);
}
if (i + 1 < N) dp[i + 1] = Math.max(dp[i], dp[i + 1]);
}
// 출력
System.out.println(dp[N-1]);
}
}그런데 예제 입력 1을 돌려보면 정답인 45가 아니라 55가 나온다.
중간에 10이 한 번 더 더해져서 그랬다..
첫 날 바로 접수를 한 상담이 3일에 끝나고, 그때 까지의 최댓값은 10으로 갱신 된다.
그리고 3일 째에 접수를 또 하면 하루만에 끝나기 때문에 새로 접수한 것을 기존에 저장돼 있는 10에 누적해서 최댓값을 갱신하다 보니, 10과 10의 비교가 아니라 10과 10+10의 비교가 되어버려서 그랬다..
끝나는 날을 한 번에 알 수가 없으니, 각각의 상담을 확인하면서 며칠이 소요되는지 확인한 후에 끝나는 날까지 가서 갱신을 했고 기존값이 지워져서 이런 일이 발생했다.
그러니 이것을 예방하려면 각 날짜마다 그 날 끝나는 상담들을 개별적으로 고려해줘야했다.
즉, N일에 끝나는 상담이 몇 개나 있는지, 그 날을 기준으로 앞에 있는 모든 상담들을 확인해보며 그것들을 한 번에 비교해야하는 것이다.
그래서 일단은 해당 날짜를 기준으로 앞에 있는 상담들을 고려하는 식으로 생각해봤다.
그렇게 하니 각 날짜별로 앞에 상담날짜를 확인해봐야 했는데, 그러면 2중 for문으로 작성해야했다.
물론 이건 N이 최대 15라서 시간초과할 일은 없겠지만, DP라면 이것보다 더 쉬운 방법이 있을 거 같았다.
그러면 어떻게 해야 그 날의 상담 여부를 고려할 수 있을지 고민해봤다.
뒤에서부터 접근하자
기발한 아이디어가 있어서 그렇게 한 건 아니지만,,, 뒤에서부터 생각을 해봤다.
문제에 적힌 케이스부터 생각해보니
뒤에 세 칸을 바로 결정할 수 있었다.
6일과 7일은 퇴사일이 지나서 끝나기 때문에 고려대상에서 제외된다.
5일은 퇴사일 전에 끝나기 때문에 가능하다.
그렇다면, 5일부터 퇴사일까지는 최대 15만큼의 수익을 얻을 수 있다.
그리고 이제 앞으로 한 칸 더 가서 4일을 보면,
1. 퇴사일 전에 끝나기 때문에 고려 대상이다.
2. 5일의 상담 수익보다, 4일의 상담 수익이 크기 때문에 4일부터 퇴사일까지 상담을 한다면 최대 수익은 20이 된다.
따라서 4일부터 퇴사일까지는 최대 35만큼의 수익을 얻을 수 있다.
마찬가지로 3일부터 퇴사일까지는 최대 45만큼의 수익을 얻을 수 있다.
앞으로 한 칸 더 가서 2일을 보면,
1. 퇴사일 전에 끝나기 때문에 고려 대상이다.
2. 2일에 상담 수익은 20이고, 이날 상담을 하면 5일이 소요되기 때문에, 7일부터 다시 상담을 할 수 있다. 그러면 최대 수익은 2일의 수익인 20이 전부이기 때문에 2일에는 상담을 하지 않고, 3일부터 상담을 하는 것이 이득이다. 그래서 2일부터 퇴사일까지의 최대 수익은 45다.
마찬가지로 한 칸 더 가서 1일을 보면, 3일까지 상담을 할 수 없고 수익은 10 발생한다. 그러면 4일까지의 최대 수익인 35에 10을 더 한 45가 된다.
따라서 퇴사일까지의 전체 최대 수익은 45가 되는 것이다.
이 과정을 따라오면서 DP배열을 이렇게 정의했다.
DP[N]는 N일부터 퇴사일까지의 최대 수익이다.
그리고 이 DP[N]는 앞에서 오는 게 아니라 뒤에서부터 결정된다.
- 그 날 상담을 하는 것이 퇴사일 전에 끝나는 지, 퇴사일 전에 끝나는 상담이라면 2번
- 그 날 상담을 해서 얻는 수익 + 상담이 끝나고 난 다음날의 최대 수익 VS 그 전날까지의 최대 수익
- 퇴사일 전에 끝나지 않는 상담이라면 고려하지 않는다.
이렇게 정리해볼 수 있다!
그렇게 1일까지 모두 고려하고 나면 최종적으로 DP배열의 처음 값에는 첫 날부터 퇴사일까지 얻을 수 있는 최대 수익이 기록된다.
이걸 N에 대한 점화식으로 나타낸다면 이렇게 할 수 있다.
N+1 일은 퇴사일
1. if N + Time[N] ≤ N+1, dp[N] = max{dp[N+1], P[N]+dp[N+T[N]]}
2. if N + Time[N] > N+1, dp[N] = dp[N+1]
이제 이걸 코드로 옮겨 적으면 된다.
정답
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N 입력 받기
int N = Integer.parseInt(br.readLine());
// 금액 입력 받기
int[] time = new int[N + 1];
int[] fee = new int[N + 1];
for (int i = 1; i < N + 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
time[i] = Integer.parseInt(st.nextToken());
fee[i] = Integer.parseInt(st.nextToken());
}
// dp
int[] dp = new int[N + 2];
for (int i = N; i >= 1; i--) {
if (i + time[i] <= N + 1) { // 마지막 날까지 끝나는 상담 = 접수가 가능한 상담: 최댓값으로 갱신
// 현재의 최대 수익 =
// 바로 전 날까지의 최대 수익 vs 현재 상담이 끝나는 날부터 퇴사일까지의 최대 수익 + 현재 상담을 접수 했을 때의 수익
dp[i] = Math.max(dp[i + 1], dp[i + time[i]] + fee[i]);
} else { // 접수가 불가능한 상담: 이전의 최대 수익을 그대로 복사
dp[i] = dp[i + 1];
}
}
// 출력
System.out.println(dp[1]);
}
}