G15486. 퇴사 2

문제

제출 코드

• 사용 알고리즘 : DP

요 근래 풀었던 DP들과는 조금 다른 경우라, 방법을 도출해내기까지 시간이 좀 걸렸다.

다른 DP들은 이전의 값을 통해 현재의 값을 구해나가는 방식이었지만, 이번 dp는 뭔가 이전의 값을 끌어 현재에 가져오고, 현재 상담을 했을때 얻게될 이익을 계산하여 미래의 값을 구해두는 방식이었다.

정리하자면, 시간 순으로 얻게 될 최대이익을 저장해나가는데 먼저 오늘 이익과 어제 이익 중 최대이익을 오늘 값에 저장한다.

이후 오늘 잡힌 상담을 했을 경우 발생할 이익을, 그 상담이 끝나는 날의 이익 값에 (어제의 이익+상담비)와 이미 저장된 이익값 중 최댓값으로 저장한다.

package gold;

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

public class G15486_leaveCompany {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int[][] price = new int[N+1][2];
		for(int i=1; i<=N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			price[i][0] = Integer.parseInt(st.nextToken());
			price[i][1] = Integer.parseInt(st.nextToken());
		}

		int[] dp = new int[N+1];

		for(int i=1; i<=N; i++) {
			dp[i] = Math.max(dp[i], dp[i-1]);

			int day = i+price[i][0]-1;
			if(day<=N) dp[day] = Math.max(dp[day], dp[i-1]+price[i][1]);
		}

		System.out.println(dp[N]);
	}

}