[백준] 15486번 : 퇴사 2

문제

 

 

접근 방식

문제 자체는 14501번 퇴사 문제와 똑같지만 입력의 양이 최대 150만 개이기 때문에

이전에 풀었던 방식처럼 O(n^2)의 시간 복잡도로 풀면 시간 초과가 발생한다.

 

DP 테이블을 좀 더 효율적으로 채워 넣어야 시간 제한을 맞출 수 있으니

문제를 좀 더 자세하게 분석해보겠다.

 

우선 i번째 날에 t일의 시간이 소요되는 상담을 진행했다면

i + 1일에 p만큼의 돈을 지급받는다.

 

즉, i일 이전에 받은 돈들은 모두 정해진 기한 내에 완료하여 받을 수 있는 돈이고

i일에 받을 수 있는 가장 큰돈은 i일 이전의 값들 중 가장 큰 값이다.

n
10

t p
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

 

위와 같은 테스트 케이스가 주어졌을 때

1일	2일	3일	4일	5일	6일	7일	8일	9일	10일	퇴사
1 + 5일					50
	2 + 4일				40
		3 + 3일			30
			4 + 2일		20
				5 + 1일	10
					6 + 1일	50 + 10
						7 + 2일		60 + 20
							8 + 3일			60 + 30
								9 + 4일		기간초과
									10 + 5일	기간초과
					50	60		80		90

 

1 ~ 5일까지의 상담들은 모두 6일에 완료되어 돈을 받을 수 있고

그중 가장 큰 값인 50원이 6일에 받을 수 있는 가장 큰 경우다.

 

다음으로 6일에 진행한 상담비는 하루 뒤인 7일에 받을 수 있고

7일에는 이전까지의 받은 돈 중 가장 큰 값인 50원에

당일 받을 10원을 더한 60원을 받을 수 있다.

 

7일에 진행한 상담비는 2일 뒤인 9일에 받을 수 있고

마찬가지로 현재까지 받은 돈 중 가장 큰 60원에

당일 받을 20원을 더한 80원을 받을 수 있다.

 

8일에 진행한 상담비는 3일 뒤인 퇴사날에 받을 수 있고

8일 이전의 가장 큰 값인 60원에 30원을 더한 90원을 받을 수 있다.

 

즉, 매 상담마다 두 가지를 계산해 주면 되는데

현재를 기준으로 가장 큰돈을 받을 수 있는 경우인 dp [i]와

현재 + 소요일에 받게 될 돈인 dp [i+t]를 구해주면 된다.

 

dp[i]는 현재 날짜와 이전 날짜 중에서 가장 큰 값을 골라주면 되니

dp[i] = max(dp[i], dp[i-1])

 

dp [i+t]는 현재 날짜에 받을 수 있는 가장 큰 돈 + 상담 완료 시 받을 돈 중에서

가장 큰 값을 골라줘야 하니

dp[i+t] = max(dp[i+t], dp[i] + p)

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		int[] dp = new int[n + 51];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());

			int time = Integer.parseInt(st.nextToken());
			int price = Integer.parseInt(st.nextToken());

			dp[i] = Math.max(dp[i], dp[i - 1]);
			dp[i + time] = Math.max(dp[i + time], dp[i] + price);
		}

		System.out.println(Math.max(dp[n], dp[n + 1]));
	}
}