DP

백준 14501번을 Java를 이용해 풀어보았다.

문제 링크 첨부한다.
https://www.acmicpc.net/problem/14501

---

점화식 찾기

오랜만에 풀어보는 DP 문제였는데 역시 점화식만 찾으면 되는 문제지만 점화식을 찾기 어려운...

나는 dp[n] 을 n번째 날부터 일 했을 때 얻을 수 있는 최대 수익이라 정의했다.

문제에서는 1일, 2일, ... 7일 로 표시했지만 나는 0일, 1일, ... 6일 로 표현했다.
i번째 날의 최대 수익을 계산하기 위한 점화식은 다음과 같다.

핵심 점화식

dp[i] = Math.max(dp[i+1], dp[i+t[i]] + p[i]);

위의 t[i] 와 p[i] 는 문제에서 주어진 i번째 날 상담에 소요되는 시간과 비용을 저장해둔 배열을 각각 가리킨다.

하나씩 살펴보자. 두 가지 경우를 살펴봐야 하는데 먼저 dp[i] = dp[i+1] 이 되는 경우부터 살펴보자.
만약 오늘이 3일인데 어제인 2일의 상담을 아직까지 다 마치지 못해서 오늘도 어제 일을 하고 있는 경우라면 dp[2]나 dp[3]이나 같을 수밖에 없다.

이번엔 두 번째 경우를 살펴보자. dp[i] = dp[i+t[i]] + p[i] 가 되는 경우다. 만약 오늘이 3일인데 지난 날에 시작되어 아직까지 진행 중인 상담이 없는 상태다. 그렇다면 3일에 할당된 상담을 진행할 수 있는 상황인 것이다. 3일의 상담에 이틀(2)이 걸리고 10의 비용이 든다면, dp[3] 은 dp[3+이틀] 에 10만큼의 비용을 더해주면 되는 것이다.

위의 두 경우 중에 dp[i] 를 더 크게 만들어주는 경우를 선택하면 되는 것이고 이를 Math.max() 를 통해 얻는 것이다!

전체 코드는 아래와 같다.

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

public class boj14501 {
    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        int N = Integer.parseInt(bfr.readLine());
        int[] time = new int[N];
        int[] price = new int[N];

        for(int i=0; i<N; i++){
            stk = new StringTokenizer(bfr.readLine());
            time[i] = Integer.parseInt(stk.nextToken());
            price[i] = Integer.parseInt(stk.nextToken());
        }

        int[] dp = new int[N+1];
        for(int i=N-1; i>=0; i--){
            if(i+time[i]>N) dp[i] = dp[i+1];
            else    dp[i] = Math.max(dp[i+1], dp[i+time[i]]+price[i]);
        }

        System.out.println(dp[0]);
    }

}

---

DP 문제는 만날 때마다 실패하는 것 같다. 너무 너무 부족함을 느낄 때에 가끔 무력함이 밀려오지만.. 꾸준하지 못했던 나를 채찍질할 뿐,,,