[DP] BOJ_14501: 퇴사

난이도가 실버3로 그리 어렵다고 할 수 없는 문제임에도 엄청나게 애를 먹었다.

 

PS를 하다 보면 이상한 데 꽂혀서 중요한 곳을 지나치고 어문 곳을 계속 빙빙 돌 때가 있는데, 그런 경우가 가장 난감한 것 같다.

 

 이 문제의 경우에는 내가 '만약 첫째 날에 잡혀 있는 일정이 너무 오래 걸려 잡을 수 없는 예약인 경우' 를 고려하지 않고, 다른 곳에서 틀렸다고 쓸데없는 확신을 하여 여기저기 손대 보다가 망한 문제이다. 아마도 지금까지 풀어 온 '~한 ~수열 찾기' 류 문제들이 당연히 첫 번째 memoization은 자기 자신, 혹은 1이 되는 문제들이었기에 이런 실수를 한 것 같다.

 

우선 문제를 풀기 위해 소요 날짜를 나타내는 duration 배열, 보수를 나타내는 payment 배열, 그리고 memoization을 위한 dp배열을 생성하였다. 

 

당연히 첫 날 예약이 잡을 수 없는 예약이면 dp[1]=0이다. 이를 구현하기 위해 아래와 같이 코드를 작성하였다.

 

        if(duration[1]>=n+1){
            dp[1]=0;
        }else{
            dp[1]=payment[1];
        }

 

이후로는 여태 풀어온 다른 dp문제를 풀듯이 이중반복문을 통해 dp 배열을 채웠다. 두 날짜 간 차이가(i-j) j일에 상담을 했을 때 소요되는 날짜보다 (duration[j]) 큰 경우, dp[i]는 이전까지의 보수 합과 i번째 날의 보수를 더한 것과 이전에 미리 업데이트해 둔 dp[i]의 최대값 중 더 큰 값이 된다. 다만 i번째 날을 선택 시 퇴사일을 초과하면 안 되기 때문에 이를 위한 조건을 덧붙여 주었다.

 

또한, 만일 j일을 선택하면 i일을 선택할 수 없는 상황인데(i-j<duration[j]), 그냥 j일까지의 보수를 싹 다 포기하고 i일 상담을 하는 것이 더 큰 보수를 가져다 준다면 그런 선택을 해야 한다. 

 

이 로직을 다음과 같이 구현하였다.

for(int i=2;i<n+1;i++){
            for(int j=1;j<i;j++){
                if(i-j>=duration[j]&&i+duration[i]<=n+1){
                    dp[i] = Math.max(dp[j]+payment[i],dp[i]);
                }else if(i-j<duration[j]&&i+duration[i]<=n+1){
                    dp[i]=Math.max(dp[i],payment[i]);
                }
            }
        }

이후로는 그냥 dp배열의 최대값을 출력하면 된다. 전체 코드를 첨부하고 마친다.

package DP;

import java.io.*;
public class BOJ_14501 {
    static int[] duration = new int[16];
    static int[] payment = new int[16];
    static int[] dp = new int[16];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=1;i<n+1;i++){
            String[] durationPayment = br.readLine().split(" ");
            duration[i] = Integer.parseInt(durationPayment[0]);
            payment[i] = Integer.parseInt(durationPayment[1]);
        }
        if(duration[1]>=n+1){
            dp[1]=0;
        }else{
            dp[1]=payment[1];
        }
        for(int i=2;i<n+1;i++){
            for(int j=1;j<i;j++){
                if(i-j>=duration[j]&&i+duration[i]<=n+1){
                    dp[i] = Math.max(dp[j]+payment[i],dp[i]);
                }else if(i-j<duration[j]&&i+duration[i]<=n+1){
                    dp[i]=Math.max(dp[i],payment[i]);
                }
            }
        }

        int max = 0;
        for(int i=1;i<n+1;i++){
            max = Math.max(max,dp[i]);
        }
        System.out.print(max);
    }
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

지적, 조언, 교정 언제나 환영합니다!