[beakjoon]퇴사 JAVA

 

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

14501번: 퇴사

 

* 이 문제를 풀기 위해선 점화식을 알고 가야한다.

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

13699번: 점화식

		//dp[i] += dp(dp[j] * dp[i-1-j]);
		//j = 0 ~ (i-1)
		long dp[] = new long[36];
		dp[0] = 1;
		dp[1] = 1;
		
 		for(int i = 2; i < 36; i++) {
			for(int j = 0; j < i; j ++) {
				dp[i] += (dp[j] * dp[i-1-j]);
			}
		}
 		
 		int count = 0;
 		for(long d : dp) {
 			System.out.println(count + " : " + d);
 			count++;
 		}

 

<주의> 

상담 날짜의 끝나는 날 기준으로 계산, 뒤에서 부터 시작해야 한다.

이런 계산식의 문젠는 손으로 써보면 이해가 확실히 잘된다!!

 

 

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 NumberFormatException, IOException {
		
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 StringTokenizer st = new StringTokenizer(br.readLine());
		 
		 int N = Integer.parseInt(st.nextToken());
		 
		 int[] time = new int[N+1];
		 int[] pay  = new int[N+1];
		 int[] dp = new int[N+2];
		 
		 for(int i = 1; i <= N; i++) {
			 st = new StringTokenizer(br.readLine());
			 time[i] = Integer.parseInt(st.nextToken());
			 pay[i] = Integer.parseInt(st.nextToken());
		 }
		 
		 int day = N+1;
		 
		 for(int i = N; i > 0; i--) {
			 
			 int next = time[i] + i; // 일 끝나는 시간
			 
			 if(next > day) dp[i] = dp[i+1];
			 else {
				 dp[i] = Math.max(dp[i+1], pay[i]+dp[next]);
			 }
		 }
		 
		 System.out.println(dp[1]);
	}
}