[백준] 14501 - 퇴사 (Java)

[백준] 14501 - 퇴사 (Java)

문제

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

풀이/후기

5월에 브루트포스 문제 풀다가 만난 문제로

그때 당시 DP 풀이를 보고나서 도망갔던 문제를 다시 풀어보았다.

이제는 DP가 익숙하지만 점화식을 세우는 것은 여전히 어려웠다...

이미 나와있는 점화식을 보고도 이해하는데 한참 걸리니,,^^;

아직도 갈 길이 멀다 싶다 ㅋㅋ 그래도 계속 보다보니 이해가 가긴 한다!

이게 어디야,,

 

dp[t[i] + i] = Math.max(dp[t[i] + i] , dp[i] + p[i]);

 

그리고 작업을 진행하지 못한 날은 0이 아니라 그 전에 최대값으로 채워줌

dp[i+1] = Math.max(dp[i], dp[i+1]);

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer str;
		int[] t = new int[N];
		int[] p = new int[N];
		
		for (int i=0; i<N; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			t[i] = Integer.parseInt(str.nextToken());
			p[i] = Integer.parseInt(str.nextToken());
		}
		
		int[] dp = new int[N+1];
		
		for (int i=0; i<N; i++) {
			int tt = t[i];
			int tp = p[i];
			
			if (i + tt <= N) {
				dp[i + tt] = Math.max(dp[i+tt], tp + dp[i] );
			}
			
			dp[i+1] = Math.max(dp[i+1], dp[i]);
		}

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

	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/43c76368c6fe20a4d45460180218b27d51f60955

참고

https://hidelookit.tistory.com/118