백준 15486번 : 퇴사2

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

 

 

 

 

 

문제

• 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
• 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
• 상담을 적절히 했을 때, 얻을 수 있는 최대 수익 구하기

 

출처 : https://www.acmicpc.net/problem/15486

 

 

제한사항

• N (1 ≤ N ≤ 1,500,000)
• 1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000

 

 

 

 

 

풀이

• 다이나믹 프로그래밍

 다이나믹 프로그래밍의 조건인 최적 부분 구조를 만족한다. 부분 문제의 최적 값을 이용해 전체 문제의 최적 값을 구할 수 있는 문제이다. 예제1의 경우를 살펴보면, 7일이 되는 날의 최댓값은 5일이 되는 날의 최댓값에서 그 날의 금액을 더한 값이 된다.

 

 어떤 날까지의 최대 금액을 저장하고, 활용해야 한다. 따라서 dp[i]는 i일까지 얻을 수 있는 최대 수익이 된다. 그리고 DP의 배열의 크기는 문제에서 N + 1째 되는 날 퇴사를 한다고 했기 때문에, 원래의 크기인 N에서 1을 더 추가해줬다. 최댓값을 구해야 하므로, DP의 초기값은 모두 0으로 초기화 한다. 

 

 

• DP 배열 채우기

 첫째날인 1일부터 N일까지 DP 배열을 채워나간다. 현재 상담을 한다고 하면, '다음 상담에 받게 될 금액'은 '현재까지의 금액의 최대값'에 '지금 상담을 할 경우의 금액'을 더한 값이 될 것이다.

 

하지만 그 값이 최대가 아닐 수도 있다.

1일	2일	3일	4일
2	2	1	1
3	15	10	5

 

 

먼저, 1일에 상담을 하면, 3일까지 3을 받을 것이다.

그리고 2일에는 상담을 하면, 4일까지 15를 받을 것이다. (이미 최댓값)

그리고 3일에는 상담을 하면 4일까지 3 + 10을 받을 것이다. 

 

dp[i + time] = Math.max(dp[i + time], dp[i] + pay)

 

 이미 앞서 최댓값이 나왔으므로, '다음 상담에 받게 될 금액'은 '현재까지의 금액의 최대값'에 '지금 상담을 할 경우의 금액'을 더한 값과 '다음 상담에 받게될 금액의 최댓값' 중 큰 값이 되어야 한다.

 

 

 

 

반례) 상담을 안하고 넘길 수도 있는 경우도 처리하기

 

예제4의 경우와 같이, 해당 일에 상담을 안하고 넘어가는 경우가 최대가 될 수도 있다.

 

 

1) 7일에 상담을 하는 경우

1일	2일	3일	4일	5일	6일	7일	8일	9일	10일
5	4	3	2	1	1	2	3	4	5
50	40	30	20	10	10	20	30	40	50

 

50 + 10 + 30 = 80

 

 

2) 7일에 상담을 안하는 경우

1일	2일	3일	4일	5일	6일	7일	8일	9일	10일
5	4	3	2	1	1	2	3	4	5
50	40	30	20	10	10	20	30	40	50

 

50 + 10 + 30 = 90 으로 더 크다.

 

 

dp[i + 1] = Math.max(dp[i + 1], dp[i])

 

 7일에서 상담을 하지 않으면, 8일에는 7일의 값을 그대로 갖게 된다. 만약 이미 최댓값이 있다면 이미 있는 최댓값이 8일의 값이 될 것이다. 

 

 

 

 

 

코드

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));
		
		int N = Integer.parseInt(br.readLine());

		int[][] arr = new int[N + 1][2];
		
		for(int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[N + 2];
		
		for(int i = 1; i <= N; i++) {
			int time = arr[i][0];
			int pay = arr[i][1];
			
			if(i + time <= N + 1) {
				dp[i + time] = Math.max(dp[i + time], dp[i] + pay);
			}
			
			dp[i + 1] = Math.max(dp[i + 1], dp[i]);
		}
		
		System.out.println(dp[N + 1]);
	}

}

 

 

 

 

결과

 

 

 

 

배운점