[백준 / 14501 퇴사 / Java / DP]

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

14501번: 퇴사

 

문제 설명

일할 수 있는 요일을 지정해서 최대 요금을 구해야하는 문제

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

DP[현재 날의 상담 기간을 계산했을 때 끝나는 날] = max(DP[현재 날의 상담 기간을 계산했을 때 끝나는 날], DP[현재 날까지 계산된 값] + pay[현재 날 상담을 통해 얻는 값])

 

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

다음날의 계산된 결과 값, 오늘날의 계산된 결과 값 중 큰 값을 다음날 값에 삽입

위의 두 식으로 해결되는 문제, 생소한 개념이라 다시 볼 것

 

import java.io.*;
import java.util.*;

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());
        
       int[] t = new int[N];
       int[] p = new int[N];
        
        StringTokenizer st;
        
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[N+1]; // 1일에 일한 돈은 2일차에 누적되기 때문
         // 날짜를 진행하면서 해당 날짜에 대한 최대 요금을 저장하는 배열, 각 배열의 인덱스마다 최대 요금을 저장해놓는다. 
        
        for(int i=0; i<N; i++){
            if(i + t[i] <= N) { 
                // 날짜가 초과되지 않으면서 해당 날짜에 번 돈을 계산
            	dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
            }
          
            // 오늘 일한 걸 다음날 누적시키기 위한 계산
            dp[i+1] = Math.max(dp[i+1], dp[i]);
        }
        System.out.println(dp[N]);
    }
}