[백준] 14501 - 퇴사 문제 풀이(자바,Java)

문제

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

 

들어가며

dp 를 잘못 생각해서 못 푼 문제이다.

 

풀이 코드

package solved.ac.maraton;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 백준14501_퇴사 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<int[]> cons = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                    .toArray();
            int t = s[0];
            int p = s[1];
            cons.add(new int[]{t,p});
        }

        int[] dp = new int[n+1];
        for (int i = 0; i < n; i++){
            int t = cons.get(i)[0];
            int p = cons.get(i)[1];

            dp[i+1] = Math.max(dp[i+1],dp[i]);
            if (i + t <= n){
                dp[i+t] = Math.max(dp[i+t],dp[i]+p);
            }
        }
        System.out.println(dp[n]);

    }
}

풀이

dp 배열엔 i 시간일 때, 최대 이익을 저장한다.

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

먼저 다음 dp[i+1] 을 계산하기 위해 이전 값과 현재 값을 비교한다.

if (i + t <= n){
    dp[i+t] = Math.max(dp[i+t],dp[i]+p);
}

그리고 i+t 한 값이, 즉 일이 끝난 다음 시간대 계산을 하기 위해서 위와 같은 계산을 한다.

dp[i]+p 와 dp[i+t] 중에 최대값을 찾아서 갱신한다.

dp[i]는 i 시간에서 최대값을 저장하기 때문에 위와 같이 계산한다.