[백준/15486] 퇴사 2 - JAVA

이지환·2025년 5월 12일

백준 알고리즘

알고리즘(백준) 💻

목록 보기

65/80

📌 문제

알고리즘 분류 : DP
난이도 : 골드5
출처 : 백준 - 퇴사 2

🦧 문제 풀이 접근

DP문제인데 색다르게 접근을 해봤다
배열에 뒤부터 접근해서 비교를 하는 방식이다.
배열 뒤에서 부터 (T_i일 후에 최대 금액+오늘의 상담 금액)과 (내일까지의 최대 상담 금액)중 큰 값이 금일 최대 상담 금액이 된다.

문제에 제시된 표를 기준으로 예를 들면

7일차

6일차

5일차

4일차

3일차

2일차

1일차

이런 형태가 된다.
DP[0]의 값이 최대 상담 금액이 된다.

💻 code

import java.util.*;
import java.io.*;
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 DP[] = new int[N+1];
        int TP[][] = new int[2][N];
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            TP[0][i] = Integer.parseInt(st.nextToken());
            TP[1][i] = Integer.parseInt(st.nextToken());
        }
        for(int i=0;i<N;i++) {
            if(TP[0][N-i-1]+(N-i-1)<=N)
                DP[N-i-1] = Integer.max(DP[N-i], DP[N-i-1+TP[0][N-i-1]]+TP[1][N-i-1]);
            else
                DP[N-i-1] = DP[N-i];
        }
        System.out.println(DP[0]);
    }
}