[Java] 백준 퇴사 2

1. 문제분석

퇴사를 하기전에 일을 열심히 한다고 한다. 대단한 사람같다.

남은 N일동안 일할 때 최댓값을 구한다고 한다. 1일부터 차근차근 해보자.

 

1일 -> 4일부터 최댓값(3일동안 아무것도 못하므로) or 현재 일하는 가치 + 지난날 까지의 최대가치

2일 -> 8일부터 최댓값(5일동안 아무것도 못하므로) or 현재 일하는 가치 + 지난날 까지의 최대가치

자세한 방법을 찾았습니다! 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.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[][] arr = new int[size + 2][2];
        int[] dp = new int[size + 2];

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

        int max = Integer.MIN_VALUE;
        for (int i = 1; i < size + 2; i++) {
            if (max < dp[i]) {
                max = dp[i];
            }

            int time = i + arr[i][0];
            if (time < size + 2) {
                dp[time] = Math.max(dp[time], max + arr[i][1]);
            }
        }
        System.out.println(dp[size + 1]);
    }
}

2차원 배열에서 첫번째 행은 시간, 두번째 행은 가치를 주었다.

for문에서 max를 계속 갱신을 해주고 시간조건에 따라서 구하면 된다.

3. 마무리

이번 문제는 조금 꼬였지만 인덱스 문제를 다시한번 생각해보는 문제였다.

인덱스로 가치를 구하는게 이제 눈에 익는다.