[BJ]백준 15486. 퇴사2

백준 15486. 퇴사2

 

 

문제링크

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

15486번: 퇴사 2

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=-4wjSUr1_K0 

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

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

/**
 * @author 은서파
 * @since 2021. 10. 19.
 * @see 
 * @performance 337344	816
 * @category #
 * @memo
 */

public class BJ_S3_15486_퇴사2{
	
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int N; // 1<=N<=1,500,000
	static int MAX;
	static int [][] data;
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		data = new int [N+1][2];
		for(int n=1; n<=N; n++) {
			tokens = new StringTokenizer(input.readLine());
			data[n][0]=Integer.parseInt(tokens.nextToken());
			data[n][1]=Integer.parseInt(tokens.nextToken());
		}// 입력 완료!!
		
		dp();
		
		System.out.println(MAX);
	}
	
	static void dp() {
		// N일째에 하루짜리 일을 하면 N+1일째가 최대 수익
		int [] dp = new int[N+2];
		for(int n=1; n<=N; n++) {
			// 오늘 작업의 결과 반영
			int next = n + data[n][0];
			if(next <=N+1) {
				dp[next] = Math.max(dp[n] + data[n][1], dp[next]);
			}
			// 오늘 한 일은 내일 정산을 받는다.
			dp[n+1]= Math.max(dp[n],  dp[n+1]);
		}
		MAX = dp[N+1];
	}

	
	// REMOVE_START
	private static String src = "7\n"
			+ "3 10\n"
			+ "5 20\n"
			+ "1 10\n"
			+ "1 20\n"
			+ "2 15\n"
			+ "4 40\n"
			+ "2 200";
	// REMOVE_END
	
}