DP - 14501. 퇴사

문제

www.acmicpc.net/problem/14501

14501번: 퇴사

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int days = Integer.parseInt(st.nextToken());
		int[] periods = new int[days + 1];
		int[] expectedSum = new int[days + 2];
		int maxExprense = 0;
		
		for (int n = 1; n <= days; n++) {
			st = new StringTokenizer(br.readLine());
			periods[n] = Integer.parseInt(st.nextToken());
			int expense = Integer.parseInt(st.nextToken());
			
			expectedSum[n] = Math.max(expectedSum[n], expectedSum[n - 1]);

			int dueDate = n + periods[n];
			if (dueDate <= days + 1) {
				expectedSum[dueDate] = Math.max(expectedSum[dueDate], expectedSum[n] + expense);
				maxExprense = Math.max(maxExprense, expectedSum[dueDate]);
			}
		}
		System.out.print(maxExprense);
	}
}

 

설명

Ti 는 당일을 포함한 값입니다.

예를 들어, 3인 경우 오늘부터 내일 모레까지 상담을 진행한다는거죠.

이 점을 명심하고 계산해야 합니다.

여러 계산 방법이 있겠지만, 1일 걸리는 상담 계산이 좀 까다로워서,

상담이 끝난 다음날에 값을 저장하여 계산했습니다.

해당 날짜와 이전날에 저장된 값을 비교하여 최대값을 가져옵니다.

그리고, 오늘 예정된 상담 날짜를 계산하여 상담할 수 있다면, 비용을 계산하여 상담이 끝난 다음날에 값을 저장합니다

이렇게 계산하며 쭉쭉 나아가면 결과가 나오죠.

 

다른 예시의 계산 결과를 볼까요?

회고

생각보다 정답률이 높아서 놀랐어요.