[백준] 14501 퇴사 / 자바(Java)

• 문제

• 해설

• 코드

문제

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

14501번: 퇴사

 

---

해설

상담이 매일 잡혀있고, 앞의 상담 여부가 뒤의 상담가능 여부를 정하기 때문에 각 일자별 최대 금액을 구하는 dp를 이용하여 문제를 해결하였다.

 

dp[i]를 해당 일자의 최대 금액이라 한다면 점화식을 이와 같이 세울 수 있다

dp[i + t[i]] = max(dp[i + t[i]] , dp[i] + p[i])

현재 i에서 상담일(t[i])를 더한 날의 최대 금액에서 오늘 일을 한 경우와 본래 있던 경우 중 최대값을 현재 최대값으로 넣어준다.

 

 

이때 dp배열의 크기는 N을 벗어나지 않으므로 조건을 추가해준다

if( i + t[i] <= N) dp[i + t[i]] = max(dp[i + t[i]] , dp[i] + p[i])

 

 

추가로 해당 일자의 최대금액은 항상 전날 이상이 되므로 사이의 일을 안한 날이 0으로 남지 않도록 조건을 하나 더 추가해 준다.

if( i + t[i] <= N) dp[i + t[i]] = max(dp[i + t[i]] , dp[i] + p[i])
dp[i+1] = max(dp[i+1],dp[i])

 

예시에 따라 해당 코드의 내용을 확인하면 다음과 같다

	1일	2일	3일	4일	5일	6일	7일
T	3	5	1	1	2	4	2
P	10	20	10	20	15	40	200
dp	0	0	0	10	30	30	45

 

i = 1  => dp[4] = max(dp[4] , dp[1]+10) = 10  , dp[1] = 0

i = 2  => dp[7] = max(dp[7] , dp[2]+20) = 20  , dp[2] = 0

i = 3  => dp[4] = max(dp[4] , dp[3]+10) = 10  , dp[3] = 0

i = 4  => dp[5] = max(dp[5] , dp[4]+20) = 30  , dp[4] = 10

i = 5  => dp[7] = max(dp[7] , dp[5]+15) = 45  , dp[5] = 30

i = 6  => dp[10] (범위 초과)                            , dp[6] = 30 (이전 최대값 가져옴)

i = 7  => dp[9] (범위 초과)                              , dp[7] = 45

---

코드

package DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_14501_퇴사 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] dp = new int[N+1];
        for (int i=0; i<N; i++) {
            if (i + input[i][0] <= N) {
                dp[i + input[i][0]] = Math.max(dp[i + input[i][0]], dp[i] + input[i][1]);
            }
            dp[i+1] = Math.max(dp[i+1], dp[i]);
        }
        System.out.println(dp[N]);


    }
}