문제
상담사가 N일 후에 퇴사한다. i번째 날에 상담을 시작하면 T[i]일이 걸리고 P[i]만큼 수익을 얻는다. 퇴사 전까지(N일 이내) 끝나는 상담만 진행할 수 있을 때 최대 수익을 구하는 문제이다.
입력
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 다음 N개의 줄에 각 날의 상담 기간 T[i]와 수익 P[i] (1 ≤ T[i] ≤ 50, 1 ≤ P[i] ≤ 1,000)이 주어진다.
출력
첫째 줄에 최대 수익을 출력한다.
예제
입력
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200출력
45풀이
핵심 아이디어: DP[i]를 i번째 날에 도달했을 때까지의 최대 수익으로 정의한다. 앞에서 뒤로 순회하면서 현재까지의 최댓값(max)을 갱신하고, i일의 상담이 완료되는 날(i + T[i])의 DP 값을 갱신한다.
DP[i]를 i번째 날 시작 시 가능한 최대 누적 수익으로 정의한다 (초기값 0).- i = 1부터 N+1까지 순회:
- 현재
max와DP[i]를 비교하여max를 갱신한다. day = i + T[i]가 N+2 미만이면DP[day] = max(DP[day], max + P[i])로 갱신한다.
- 현재
DP[N+1]이전까지의max가 최종 정답이다.
이 방식은 O(N) 시간으로 퇴사 문제를 해결하며, N이 최대 1,500,000이므로 O(N²) DP는 시간 초과가 발생한다.
코드
import java.io.*;
import java.util.*;
public class Day374BOJ15486퇴사2DP {
static int[] T, P;
static int N;
static int max;
static int[] DP;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
T = new int[N + 2];
P = new int[N + 2];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(in.readLine());
T[i] = Integer.parseInt(st.nextToken());
P[i] = Integer.parseInt(st.nextToken());
}
DP = new int[N + 2];
for (int i = 1; i < N + 2; i++) {
if (max < DP[i])
max = DP[i];
int day = i + T[i];
if (day < N + 2)
DP[day] = Math.max(DP[day], max + P[i]);
}
System.out.println(max);
}
}복잡도
- 시간: O(N) — 1회 순회로 DP 완성
- 공간: O(N) — T, P, DP 배열