[백준/JAVA] 15486번: 퇴사 2

🔺 문제

15486번: 퇴사 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] T; // 시간 배열
    static int[] P; // 금액 배열 
    static int[] DP; // DP 배열
    static int max;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        T = new int[N + 2];
        P = 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());
        }
        
        // DP[i] : i일까지 일했을 때 버는 최고 금액
        DP = new int[N + 2];    // 🔔 범위!! 🔔
        for(int i = 1 ; i < N + 2 ; i++) {
            if(max < DP[i])
                max = DP[i];
                
            int day = i + T[i];
            if(day < N + 2) 
               DP[day] = Math.max(DP[day], max + P[i]);
        }
        
        System.out.println(max);
    }
}

✅ 해결 아이디어
✔ DP
- DP[ i ] : i일까지 받을 수 잇는 최대 상담 금액

 

 

💥 유의사항

• 마지막 날인 N일에 만약 T = 1이라면 일을 할 수 있으므로, DP 배열의 크기는 N +2 이고, DP 값은 1 ~ N + 1 까지 받는다. (참고)

 

---

🔺 다른 풀이들

- 과정 설명 감사합니다..

[BOJ] 백준 15486번 퇴사 2 (Java)

 

 

- 범위 설정에 대한 친절한 설명 굿..

백준 15486번 (DP) - 퇴사 2 (JAVA) 문제 풀이

---

💬 느낀 점

DP 늪에 입성했다...

저번에 본 문제 같아서 풀 수 있겠는데...하고 좀 고민하다가 결국 다른 분 풀이 보고 코드 제출했다...

 

 

 

1회독	2회독	3회독	4회독	5회독
V	1.20

---

(참고)

백준] 15486 퇴사2 ( DP/ Java )