백준_퇴사_14501

//알고리즘

1. dp(다이나믹 프로그래밍)

2. dp Table 생성 

3. 퇴사일을 기준으로 하루씩 줄여가면서 최대값을 갱신

4. 1일차까지의 최대값을 계산한 후 dp[1] 출력

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

public class 퇴사_14501 {

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

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

		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			T[i] = Integer.parseInt(st.nextToken());
			P[i] = Integer.parseInt(st.nextToken());
		}

		// 알고리즘
		for (int i = N; i >= 1; i--) {
			if (i + T[i] > N + 1) {
				dp[i] = dp[i + 1];
			} else {
				if (P[i] + dp[i + T[i]] > dp[i + 1])
					dp[i] = P[i] + dp[i + T[i]];
				else
					dp[i] = dp[i + 1];
			}
		}

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

}

 

※ dp를 공부하기 전 여러번 시도해봤지만 못 풀었던 문제

dp 문제를 여러개 풀어보니까 이제 규칙이 보이기 시작해서 풀었다. 

dp가 코드는 짧아도 생각하는데 시간이 걸려 다른 탐색문제 보다 훨씬 오래 걸린다. 조금 더 공부를 해봐야 할거같다.