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

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

15486번: 퇴사 2

---

 

✏️ 문제

해당 문제는 백준 14501번 (DFS) - 퇴사 문제와 같지만, 시간 복잡도가 O(N) 으로 해결을 해야 통과할 수 있는 문제입니다.

14501번: 퇴사

---

 

🔐 문제 해결

이번에는 DP로 문제를 풀어야합니다. 차근차근 함께 살펴보겠습니다.

 

1. 테이블 정의

• 먼저 dp[i]를 i일 까지 받을 수 있는 최대 상담 금액이라고 정의하겠습니다. (단, 1 <= i <= N+1)
• N(퇴사일) + 1일에 상담이 끝나도 인정이 되기 때문에 dp배열의 크기를 N+2로 하였습니다.

// i일까지 받을 수 있는 최대 상담 금액
int[] dp = new int[N+2];

 

2. 점화식 세우기

점화식에 앞서 우리는 먼저 MAX 값과 해당 값의 인덱스를 담을 배열이 필요합니다.

// MAX[0] = 최댓값의 인덱스, MAX[1] = 최댓값
int[] MAX = new int[2];

왜 필요한지 아래에서 살펴보도록 하겠습니다.

예를 들어 입력이 아래와 같이 주어진다고 가정해보겠습니다.

3
1 5
3 1
1 3

 

i = 1 인 경우

i가 1일 때, 상담이 끝난 날 (i + T[i])의 값은 2가 됩니다.

i가 2일 때를 보면 T[2] = 3이므로, 해당 상담은 퇴사일이 지났으므로 할 수가 없습니다.

그렇다면 dp[2]에는 P[i]의 값이 저장되어야 합니다.

하지만 여기서 끝이 아니라, 2일에 있는 상담을 하지 않고 3일에 있는 상담을 한다면? 5+3 = 8이되어 최대값이 될 것입니다.

이제 이것을 어떻게 점화식으로 나타내는지 알아보겠습니다.

 

먼저 1부터 N까지 for문을 돌면서 MAX값을 비교하여 값을 넣어줍니다.

for(int i=1; i<=N; i++) {
    // 최댓값 설정
    if(MAX[1] < dp[i]) {
        MAX[0] = i;
        MAX[1] = dp[i];
    }
}

 

그 다음 체크해야할 사항들이 있습니다.

• 오늘(i) 상담을 하고 나면 퇴사일(N)+1 까지 끝낼 수 있는지 확인을 해야합니다.
• 오늘 상담이 가능하다면, MAX값으로 지정된 날이 오늘보다 이전인지 확인 해야합니다.
  • 오늘보다 이전이라면, MAX + P[i] 을 dp[next]에 넣어줍니다. (값을 넣어줄 때 반드시 최대값을 넣어줘야합니다.)
  • 오늘보다 이후라면, dp[i] + P[i] 값을 dp[next]에 넣어줍니다.

int next = i + T[i];
if(next <= N+1) {
    // 최댓값인 날이 상담끝나는 날 이전이라면
    if(i > MAX[0]) {
        dp[next] = Math.max(dp[next], MAX + P[i]);
    }else {
        dp[next] = Math.max(dp[next], dp[i] + P[i]);
    }
}

 

3. 초기값 설정

dp배열의 모든 원소를 0으로 초기화합니다.

---

 

🗝 전체 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(bf.readLine());

        int[] T = new int[N+1];
        int[] P = new int[N+1];
        int[] dp = new int[N+2];

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(bf.readLine());

            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        // [0] = 최대 값의 인덱스 저장, [1] = 최대 값 저장
        int[] MAX = new int[2];

        // 1부터 탐색
        for(int i=1; i<=N; i++) {
            // 오늘 상담이 끝나는 일 계산
            int next = i + T[i];

            if(MAX[1] <= dp[i]) {
                MAX[0] = i;
                MAX[1] = dp[i];
            }
            // 만약 퇴사일+1에 끝난다면?
            if(next <= N+1) {
                // 상담이 끝나는 날이 최대값의 인덱스보다 크거나 같다면, 
                // i일 상담은 이익이 적다는 뜻이므로, 최대값 + P[i] 합을 dp[next] 에 넣어줍니다.
                if(next > MAX[0]) {
                    dp[next] = Math.max(dp[next], MAX[1] + P[i]);
                }else {
                    dp[next] = Math.max(dp[next], dp[i] + P[i]);    
                }
            }
        }

        int result = 0;
        for(int i : dp) {
            System.out.println(i);
            if(result < i)    result = i;
        }
        System.out.print("result : " + result);
    }
}