[BOJ14501 - Java] 퇴사문제 DP로 풀이하기

위 문제는 구현을 중심으로 생각하고 풀었던 문제이지만 부가적인 개념이 필요했다.

다른 스터디원은 DFS로 생각하고 구현하였으며, 나는 DP를 생각하고 풀었다.

 

우선적으로 DP를 활용하여 생각할 때 각 날짜별로 최대값을 저장해야 한다.

DP라는 배열을 만들고 각 날짜별로 받을 수 있는 급여의 최대값을 저장한다.

만약 1일에서 T1이 7이고 P1이 30이라면  DP[0] (1일) 은  최대값이 30이 될 것이다. 1일 이후에 dp[0]의 값이 변동될 수 없기 떄문에 고정이다.

 

[테스트] 만약 1일에서 T1이 2이고 P1이 30, 2일에서 T1이 1이고 P1이 50이라면 어떻게 생각할까?

첫 과정 -> 1일에서 dp[0]의 값은 30, dp[1]의 값은 이어서 30일것이다.

두번째 과정 -> 2일에서 dp[1]의 값은 30과 50을 비교하여 더 큰값인 50이 저장된다.

 

이 테스트를 기반으로 DP의 알고리즘 개념이 진행된다. 모든 선택가능한 조합을 진행하며 최대값을 저장하는 것이다.

코드로 구현해보자.

 

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

public class 퇴사_14501 {
    static int N;
    static int[] t, p;
    static int[] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        t = new int[N];
        p = new int[N];
        dp = new int[N + 1];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        // dp[i] = i일까지 얻을 수 있는 최대 수익
        for (int i = 0; i < N; i++) {
            // i일에 작업을 수행하는 경우
            if (i + t[i] <= N) {
                dp[i + t[i]] = Math.max(dp[i + t[i]], dp[i] + p[i]);
            }
            // i일에 작업을 수행하지 않는 경우
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);
        }

        // 최대 수익은 dp 배열에서 가장 큰 값
        int max = 0;
        for (int i = 0; i <= N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
}

 

 

for구문에서 만약 i+t[i] <= N 인 경우, 다시말해 정해진 날짜 안에 일을 할 수 있는 경우에는  dp[i] + p[i]  값을 기존의 p[i+t[i]] 값과 비교하여 더 큰 값으로 업데이트할 수 있다. 여기서 dp[i] + p[i]는 기존d[i]에서 벌었던 최대값에서 i+ t[i] 날짜에 추가로 일한 급여를 더한 값이다. 그래서 dp[i] + t[i] 와 dp[i] + p[i] 를 비교해서 더 큰 값을 dp[i+t[i]]에 넣는 것이다.  

다시 말하자면 dp[i+t[i]]에는 이전에 진행하면서 업데이트된 최대값이 들어있고 p[i]+t[i]는 현재 로직의 진행중인 값의 최대값이다. 이렇게 비교하면 각 dp의 요소에는 날짜별 받을 수 있는 최대 급여가 삽입되어 있다.