[java] 14501번 퇴사

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

범위가 크므로 dp를 사용하여 해결

점화식을 세워보자! ( 상담일수 배열 DayArr, 이익 배열 MoneyArr )
우선,상담일수에 따른 최대이익으로 세워야하므로? dp[상담일수] = 최대이익

i일 일 때, 걸리는 상담일수 = dp[i + DayArr[i]]

위 문제 스크린샷 예시로 보면,
1일 일 때 소요 3일, 이익 10
상담일수가 3일 소요되므로, 4일에 상담 끝.
그럼 4일 이익 = 1일째에 상담을 진행했을 때 이익 을 넣어주면 된다.
(그 사이에는 상담을 진행할 수 없기 때문에)

따라서, dp[1일 + 상담소요일수 3일] = dp[4] = 10

---

그럼, 2일 일 때는 소요 5일, 이익 50
dp[2일 + 소요 5일] 이므로, 7일에 끝나서
dp[7] = 50 이 된다.

---

3일 일때는, 소요 1일, 이익 10
dp[3일 + 소요 1일] = dp[4] = 10 이 된다.

그럼, 1일 일 때와 3일 일 때는 4일에 동시에 끝나므로
우리는 이 중 최댓값을 구해야 한다. (이 예시에서 이익은 10으로 똑같지만..)

여기서 3일 때 최댓값을 계산하려면?
1일째에 기억해두었던 dp[4] = 10 이므로,
지금 계산할 dp[3일 + 소요 1일] 과, 기억하고 있는 dp[4] 값을 비교해주면 된다.
dp[3일 + 소요 1일] = Math.max(dp[3일 + 소요1일], dp[4])

dp[3일 + 소요 1일] = dp[i] + MoneyArr[i]
dp[4] = dp[i+DayArr[i]]

구럼 dp[i+DayArr[i]] = Math.max( dp[i+DayArr[i]] , dp[i] + MoneyArr[i])
라는 점화식을 얻을 수 있다.

---

4일 일 때 한 번 더 적용하면 이해하기 쉬울 것 이다.

4일 일 때는 소요 1일, 이익 20 이므로, 5일에 끝나게 된다.
5일의 최대 이익은,
3일 상담 진행 ->4일 상담끝 , 4일 상담 진행 -> 5일끝 으로,
3일 상담 이익 (10) + 4일 상담 이익(20) = 30이 저장되어야 한다.

3일 상담 이익은 ? dp[4]
4일 상담 이익은 ? MoneyArr[4]
( dp[4]는 우리가 위 3일째 과정을 통해, 1일 상담 이익 or 3일 상담 이익 중 최댓값을 기억해 두었다.)

로, dp[5] 는 dp[4] + MoneyArr[4] == dp[i] + MoneyArr[i]

---

상담은 계속 되기 때문에, 끝난 시점에만 값을 넣어주면 안된다.
중간에도 값을 유지할 수 있어야 하므로
~> dp[i+1] = Math.max(dp[i],dp[i+1]);
도 추가해준다.

3. 코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int N;
	static int[] DayArr;
	static int[] moneyArr;
	static int[] dp;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
		DayArr= new int[N];
		moneyArr = new int[N];
		dp = new int[N+1];

		for(int i=0;i<N;i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			int day = Integer.parseInt(st.nextToken());
			DayArr[i] = day;
			int money = Integer.parseInt(st.nextToken());
			moneyArr[i] = money;
		}

		for(int i=0;i<N;i++){
			if(i+DayArr[i] <= N){
				dp[i+DayArr[i]] = Math.max(dp[i] + moneyArr[i],dp[i+DayArr[i]]);
			}
			dp[i+1] = Math.max(dp[i],dp[i+1]);
		}
		System.out.println(dp[N]);
	}
}