[백준] 14501번 퇴사 (java)

boj14501 퇴사) https://www.acmicpc.net/problem/14501

문제)
N+1일째 되는 날 퇴사를 하는데 N일 동안 최대한 많이 상담을 하여 얻을 수 있는 최대 수익을 구하기

위와 같은 상담표가 있다고 했을 때 1일, 4일, 5일에 상담을 하게 된다면 총 45 만큼의 수익을 얻을 수 있다.

[ dp를 이용한 풀이 ]

dp 배열에 저장될 값은 i일에 얻을 수 있는 최대 금액이며 최종적으로 구해야할 값은 dp[N+1]에 저장된다.

for문을 1부터 N까지 돌면서 각 일자에 상담을 진행했을 때 상담 종료 후 받을 수 있는 금액을 dp배열에 계속해서 갱신해준다.

• 1일차(t=3, p=10) 에 상담
  -> 종료 후 4일차에 10만큼 얻을 수 있다.
  

• 2일차(t=5,p=20)에 상담
  -> 종료 후 7일차에 20만큼 얻을 수 있다.
  

• 3일차(t=1,p=10)
  

• 4일차(t=1,p=20) 상담 진행
  -> dp[5] = dp[4] + p[4]
  

• 5일차(t=2, p=15)
  -> dp[7] = dp[5] + p[5]
  

• 6일차, 7일차의 경우 상담을 진행할 경우 상담종료일자가 퇴사일자를 넘어가기 때문에 상담을 진행하지 못함 !!

따라서 for문을 모두 돌게되면 최종적으로 출력되는 dp배열은 아래와 같으며 결과적으로 N+1일째 되는 날 45만큼의 최대금액을 얻을 수 있음.

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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        int[] t = new int[N+1]; // 기간
        int[] p = new int[N+1]; // 금액
        // 1일부터 시작 ~ N+1일에 퇴사하므로 범위를 N+2로 지정
        int[] dp = new int[N+2];

        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1;i<=N;i++){
            if(i+t[i]<=N+1){
                dp[i+t[i]] = Math.max(dp[i+t[i]],dp[i]+p[i]);
            }
            dp[i+1] = Math.max(dp[i+1],dp[i]); // 0일 경우 대비하여 이전값으로 갱신
        }

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



    }
}