문제 : https://www.acmicpc.net/problem/14501

Key Points

위의 상담 일정표에서 확인 할 수 있듯이 힌트를 얻을 수 있다. 백준이는 오늘로부터 N+1일째 되는 날 퇴사를 한다. 그래서 남은 N일 동안 최대한 많은 상담을 하려 한다.
1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다.
마찬가지로 2일에 있는 상담을 하게 되면, 3,4,5,6일에 잡혀있는 상담을 할 수 없게 된다.

Explain

문제를 위한 점화식을 도출해보자.
dp[N] = N일까지 얻는 이익 이라 하자.
N일을 기준으로 N일 이전에 이익을 얻을 수 있는 경우를 모두 비교하면 된다.

dp[5] = Max(5일의 이익 + 1일까지의 이익, 5일까지의 이익)
dp[5] = Max(5일의 이익 + 2일까지의 이익, 5일까지의 이익)
dp[5] = Max(5일의 이익 + 3일까지의 이익, 5일까지의 이익)
dp[5] = Max(5일의 이익 + 4일까지의 이익, 5일까지의 이익)

위와 같이 dp 배열의 값을 문제의 조건을 성립시켜 가면서 갱신해 나간다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Exam14501 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		// test_case 입력 받는다.
		int max = 0; // 최대값
		int[] T = new int[N+1]; // 상담하는데 걸리는 기간 T
		int[] P = new int[N+1]; // 상담하는데 드는 비용 P
		int[] dp = new int[N+1]; 
		
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
			T[i] = Integer.parseInt(st.nextToken());
			P[i] = Integer.parseInt(st.nextToken());
			dp[i] = P[i];
			
		}
		
		// dp[N] = N일때까지 얻은 이익
		
		// 처음 상담은 두 번째 for문에서 등장함.
		
		for(int i=2;i<=N;i++) {
			for(int j=1;j<i;j++) {
				if(i-j >=T[j]) { // 처음 상담 기간을 지나고 계속해서 갱신하기 위함
					dp[i] = Math.max(P[i]+dp[j], dp[i]);
				}
			}
		}
		// dp 배열이 갱신된다.
		
		// 갱신된 배열을 가지고 max 값을 찾는다.
		for(int i=1;i<=N;i++) {
			if(i+T[i]<=N+1) {
				if(max<dp[i]) {
					max = dp[i];
				}
			}
		}
		System.out.println(max);
		
		
	}

}