백준 : 14501 : 퇴사 (DP)

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

14501번: 퇴사

이번문제는 DP 문제 중에서 난이도가 낮은 문제라고 생각된다.

 

규칙을 찾기도 쉽고, 구현하는것도 할만하기 때문이다.

 

다만, 처음에는 최대값을 생각하지 않고, 해당 날짜에서 순차적으로 선택했을때의 결과를 DP에 넣고, 그중 가장 큰 값을 반환하게 하였으나,

 

마지막 예제에서 잘못된 결과가 반환되는것을 보고, 잘못 생각한것을 알 수 있었다.

 

이문제에서의 포인트를 살펴보자.

 

여기서의 포인트는 역순으로 DP를 입력하는것이다.

그 이유는 현재 위치에서 선택할수 있는 최대금액을 뽑는것이고, 그것이 마지막에서 앞으로 갈 수록 도출한 결과를 중복해서 사용할 수 있기 때문이다. 앞에서 부터 시작시 매번 새로운 결과를 도출해야한다.

 

i.    =  1     2    3   4   5  6   7   8   9  10

t[]   = 5    4    3    2  1   1   2   3   4   5  

p[]  = 50 40 30 20 10 10 20 30 40 50

dp[]=                            30 30 30   X   X (역순으로 실행)

 

점화식 : dp[5] = p[5] + dp[6~10까지중 최대값]

결과     : dp[5] = 10 + 30 = 40

 

내가 혼동했던 부분은 내가 i=7인 부분을 구할때, 무조건 결과가 20이 나와야 된다고 생각했는데, 차라리 i=7이지만 i=7에 일하지 않고 i=8에 일하면 30이라는 더 큰 금액을 얻을 수 있다는 점을 놓쳤기 때문이다. 

import java.util.*;

class Main {

	static int n, max = 0;
	static int[] t, p, dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		sc.nextLine(); // 버퍼

		// 초기화
		t = new int[n + 1];
		p = new int[n + 1];
		dp = new int[n + 1];

		// 입력
		for (int i = 1; i < n + 1; i++) {
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			int a = Integer.parseInt(stArr[0]);
			int b = Integer.parseInt(stArr[1]);

			t[i] = a;
			p[i] = b;
		}

		for (int i = n; i >= 0; i--) {
			int nextIndex = i + t[i];
			if(nextIndex > n+1) { //범위체크
				continue;
			}
			
			int maxInt = 0;
			for (int j = nextIndex; j < n + 1; j++) {
				maxInt = Math.max(dp[j], maxInt); //지금 이후의 상담가능한 곳부터 ~ 마지막까지 상담금액이 제일큰 수를 찾는다.
			}
			dp[i] = p[i]+ maxInt; //지금의 상담금액 + 이후의 최대 상담가능 금액의 합
		}

		for (int i = 0; i < n + 1; i++) {
			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}