[백준 15586] 퇴사2 (JAVA)

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

15486번: 퇴사 2

 

dp문제로, 배열을 생성하여 n번쨰 날짜에 받을 수 있는 돈을 저장한다.

그리고 for문을 돌면서 가장 큰 값을 max로 넣고, 배열에 가장 큰 값을 넣는다.

 

이 문제의 핵심은 하루 걸리는 업무가 마지막날 존재한다면 해당 업무는 할 수 있는 것이기에,

n+2까지 진행해야한다는 것이다.!!

 

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

class Work {
	int day;
	int cash;

	public Work(int day, int cash) {
		this.day = day;
		this.cash = cash;
	}
}

public class Main {
	static int n;
	static int[] dp;
	static Work[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st;
		arr = new Work[n + 2];
		dp = new int[n + 2];
		for (int i = 1; i < n + 1; i++) {
			st = new StringTokenizer(br.readLine());
			int day = Integer.parseInt(st.nextToken());
			int cash = Integer.parseInt(st.nextToken());
			Work w = new Work(day, cash);
			arr[i] = w;
		}
		int max = 0;
		for (int i = 1; i < n + 2; i++) {
			if (max < dp[i])
				max = dp[i];
			if (i < n + 1) {
				Work w = arr[i];
				if (i + w.day <= n + 1)
					dp[i + w.day] = Math.max(max + w.cash, dp[i + w.day]);
			}
		}
		System.out.println(max);
	}

}