[Java] 백준 퇴사

1. 문제분석

사실 이전에 퇴사2 문제를 먼저 풀고 풀어서 그런지 쉽게 풀었다.

퇴사 2에서는 구글링을 해도 이해가 안갔지만 하루동안 찾아보니 스스로 해결책을 알아버렸다.

 

일단 이 문제는 dp로 풀 수 있다. 만약 i일 때 일을 했다면 그 때 dp테이블의 값을 구하면 되는 것이니까.

노션에 이미 정리한 글이므로 복사해왔다. 그럼 하나씩 하기전에 2가지 조건을 세워서 해보자.

1. 돈은 다음날 받는다.
   • 예를 들어 1일날 일했으면 3일동안은 상담을 해야합니다.
   • 그렇다면 1, 2, 3일은 다른 상담을 못하고 1일만의 상담을 해야합니다.
   • 돈은 상담을 마치고 다음날에 들어오는 것으로 기준을 잡았습니다.(1일 → 4일)
2. 내가 n일에 일했을 때, 나오는 값(점화식)
   • 내가 1일에 일했다 → 4일부터 일 가능 → 4일까지의 최댓값 vs 1일까지 받은 돈 + 1일의 가치
   • 내가 2일에 일했다 → 7일부터 일 가능 → 7일까지의 최댓값 vs 2일까지 받은 돈 + 2일의 가치
   • 위와 같은 기준으로 나온 식은 dp[현재날짜 + 소요날짜] = dp[현재날짜 + 소요날짜] or dp[현재날짜] + 현재날짜의 가치
   • 또한 현재 시점까지의 최댓값을 알기위해 max를 지속적으로 갱신한다.

※ max를 지속적으로 갱신하는 이유는 무엇일까?

일단 갱신하는 부분이 없다 생각하고 구해보겠습니다.

• dp[1 + 3] = Math.max(dp[1+3], dp[1] + p[1]) → dp[4] = Math.max(0, 0 + 10) → dp[4] = 10
• dp[2 + 5] = Math.max(dp[2+5], dp[2] + p[2]) → dp[7] = Math.max(0, 0 + 20) → dp[7] = 20
• dp[3 + 1] = Math.max(dp[3+1], dp[3] + p[3]) → dp[4] = Math.max(10, 0 + 10) → dp[4] =10
• dp[4 + 1] = Math.max(dp[4+1], dp[4] + p[4]) → dp[5] = Math.max(0, 10 + 20) → dp[5] = 30
• dp[5 + 2] = Math.max(dp[5+2], dp[5] + p[5]) → dp[7] = Math.max(20, 30+15) → dp[7] = 45
• dp[6 + 4] → 일수가 초과되므로 선택하지 않습니다.
• dp[7 + 2] → 일수가 초과되므로 선택하지 않습니다.

dp[7]에 지금 값이 나온 상태지만 우리의 기준은 다음날 돈을 받는다 입니다.

하지만 우리는 6일차 부터 새로운 일을 시작하지 못합니다. 결국 지난날 받았던 돈을 사용하는 것이죠.

이렇게 말해서도 잘 모르시겠다면 테스트케이스 3을 보겠습니다.(dp 테이블은 한번 구해보세요..!)

• 테스트 케이스 3은 10일까지 일할 수 있습니다.
• 1일에 (5,10) → 5일걸리고 10의 가치, 6일에 (5,10) → 5일걸리고 10의가치가 됩니다.
• 그래서 돈을 받는 날, 11일에 딱 20의 가치를 받을 수 있습니다. 이런식으로 구할 때는 max가 필요없습니다. 마지막에 최댓값이 나오게 되니깐요.

결과적으로 계산식 자체에는 크게 영향을 미치지 않지만 마지막 결과를 구할 때 값이 다르게 나옵니다.

2. 구현

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[][] arr = new int[2][size + 2];
        int[] dp = new int[size + 2];
        for (int i = 1; i <= size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[0][i] = Integer.parseInt(st.nextToken());
            arr[1][i] = Integer.parseInt(st.nextToken());
        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= size + 1; i++) {
            if(max < dp[i]){
                max = dp[i];
            }
            int time = i + arr[0][i];
            if (time <= size + 1) {
                dp[time] = Math.max(dp[time], max + arr[1][i]);
            }
        }
        System.out.println(max);
    }
}

size + 2를 해준 이유는 위에서 언급한대로 구현해준 것이다.(dp는 1부터 시작, 마지막 날 + 1까지)

3. 마무리

암만 생각해도 이게 퇴사2랑 다른게 뭘까..?
퇴사 2처럼 구현했는데 통과해버린 문제..