문제
퇴사까지 N일이 남았을 때, 하루에 하나의 상담을 선택할 수 있다. 각 상담은 소요 기간 T와 금액 P로 구성되며, i일에 시작한 상담은 i+T-1일까지 이어져 그 사이에 다른 상담을 할 수 없다. 퇴사일(N+1일) 이전에 모두 완료할 수 있는 상담들을 조합하여 최대 수익을 구하는 DP 문제다.
입력
- 첫째 줄: 남은 날 수 N (1 이상 15 이하)
- 둘째 줄부터 N개 줄: i일의 상담 소요 기간 T와 금액 P
출력
최대 수익을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 | 45 |
풀이
dp[i]를 i일에 도달했을 때의 최대 수익으로 정의하고, 앞에서 뒤로 전파하는 방식(forward DP)을 사용한다.
dp[n+1]크기 배열 초기화(모두 0)- i일을 0부터 n-1까지 순회
- i일 상담을 수행하면 완료 시점은
i + t[i]일 → 해당 날짜 dp 값 갱신:dp[i+t[i]] = max(dp[i+t[i]], dp[i] + p[i]) - 상담 선택 안 하면 다음 날로 수익 이월:
dp[i+1] = max(dp[i+1], dp[i]) dp[n]이 최대 수익
핵심 아이디어: 상담 완료 시점에 수익을 직접 전파하므로, 퇴사일을 초과하는 상담은 자동으로 배제되어 별도의 경계 처리가 필요 없다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day130BOJ14501퇴사DP { // 14501 퇴사
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int n = Integer.parseInt(br.readLine());
int[] t = new int[n];
int[] p = new int[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
t[i] = Integer.parseInt(st.nextToken());
p[i] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[n + 1];
for (int i = 0; i < n; i++) {
if (i + t[i] <= n)
dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
dp[i + 1] = Math.max(dp[i + 1], dp[i]);
}
System.out.println(dp[n]);
br.close();
}
}복잡도
- 시간: O(N) — dp 배열을 한 번 순회
- 공간: O(N) — dp, t, p 배열