[백준 - 15486][Gold 5] - 퇴사 2 (JAVA)

문제 링크

---

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

 

문제

---

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)

 

출력

---

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

 

구현으로 풀릴까??

---

우선 가장 쉬운 방법인 구현을 생각해보자. 상담이 매일 1개씩 있으므로 가능한 모든 상담의 조합을 선택해 얻을 수 있는 최대 금액을 구하면 될 것이다. 위의 방법을 이용한 시간복잡도를 계산하면 다음과 같다.

 

O(n) = (모든 상담을 고르는 조합)
= 2^n

 

N은 최대 1,500,000이기 때문에 최대 연산 횟수는 2^1,500,000이다. 이는 제한시간인 2초의 추정 연산 횟수인 2억보다 훨신 큰 값이므로 제한 시간 내로 해결할 수 없다. 우리는 다른 방법을 찾아야 한다.

 

DP로 풀릴까??

---

최대 수익이기 때문에 DP로 풀릴 수 있을지 생각해 보자. DP적인 생각을 하기 위해선 큰 문제를 작은 문제로 나누어야 한다. 그러면 N일차의 최대값을 구하기 위해 1일차부터 N일차까지 최대값을 구해보자. 예제 1번의 일차별 최대값을 구하면 다음과 같다.

 

	1(일차 최대값)	2	3	4	5	6	7
3(걸리는 시간), 10(수익)	0	0	10	0	0	0	0
5, 20	0	0	10	0	0	20	0
1, 10	0	0	10	0	0	20	0
1, 20	0	0	10	30	0	20	0
2, 15	0	0	10	30	30	45	0
4, 40(불가)	0	0	10	30	30	45	0
2, 200(불가)	0	0	10	30	30	45	45

 

규칙을 알겠는가?? 위의 표를 체우는 과정을 살펴보면 다음과 같다.

 

1일차)
1일차의 최대값 = max(전날(0일차)의 최대값, 현재일(1일차)의 최대값) = max(0, 0 ) = 0

1일차의 작업을 진행할 시
현재 작업을 했을 때의 최대값 = max(전날(0일차)의 최대값 + 수익, 작업이 끝나는 날의 최대값) = max(0+10,0) = 10
3일차의 최대값 = 10


2일차)
2일차의 최대값 = max(전날(1일차)의 최대값, 현재일(2일차)의 최대값) = max(0, 0) = 0

2일차의 작업을 진행할 시
현재 작업을 했을 때의 최대값 = max(전날(1일차)의 최대값 + 수익, 작업이 끝나는 날의 최대값) = max(0+20,0) = 20
6일차의 최대값 = 20


3일차)
3일차의 최대값 = max(전날(2일차)의 최대값, 현재일(3일차)의 최대값) = max(0, 10) = 10

3일차의 작업을 진행할 시
현재 작업을 했을 때의 최대값 = max(전날(2일차)의 최대값 + 수익, 작업이 끝나는 날의 최대값) = max(0+10,10) = 10
3일차의 최대값 = 10


...

 

위의 반복을 통해 우리는 다음과 같은 점화식을 만들 수 있다!

 

최대 수익[현재 일] = max(전날 수익금에서 변동이 없을 때, 현재일에 작업을 마무리 했을 때의 수익)
= max(최대 수익[이전 일] , 최대수익[현재일])

최대 수익[작업 마무리 일] = max(이전 작업 마무리일의 최대값, 현재일에서 작업을 했을때 얻는 수익)
= max(최대 수익[작업 마무리 일] , 최대수익[현재일] + 수익)

 

위의 점화식을 적용한 시간복잡도를 계산하면 다음과 같다.

 

O(n) = (N일차의 최대 수익)
= N 

 

시간복잡도가 N이므로 최대값인 1,500,000의 연산이 발생하면 최대 1,500,000회 연산이 실행된다. 이는 2초의 예상 연산시간인 2억보다 작으므로 제한시간내에 해결할 수 있다! 위의 점화식을 코드로 구현해 문제를 해결해보자.

 

코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
class Main {
	public static void main(String[] agrs) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] benefits = new int[N+1]; //N일차 일때 받는 최대 이익
		int max = 0; //1~N일차 까지의 최대 이익
		
		for(int i=1; i<=N; i++) {
			String[] input = br.readLine().split(" ");
            //현재일의 최대값을 이전 날짜의 최대값으로 기본값 설정
			benefits[i] = Math.max(benefits[i-1], benefits[i]);
			
			int time = Integer.parseInt(input[0]);
			int price = Integer.parseInt(input[1]);
			
            //퇴사일 이후에 마무리되는 작업이면 패스
			if(i + time - 1 > N) {
				continue;
			}
			
            //현재 작업을 마무리하는 일자의 현재 최대값과 
            //현재 날짜의 최대 이익 + 현재 작업의 비용을 비교해서 큰값을 저장 
			benefits[i+time-1] = Math.max(benefits[i+time-1], benefits[i-1] + price);
            
            //최대값 갱신
			max = Math.max(max, benefits[i+time-1]);
		}
		
		System.out.println(max);
	}
}

 

 

실행 결과

---

 

 

제한시간인 2초 안에 문제가 해결되었다!

 

 

키워드

---

• 최대 수익
  
  • 구현, DP, 그리디의 가능성을 가지고 있다.