[백준-자바] N_14501 퇴사

📜 문제

• 퇴사 전까지 돈을 땡기고 싶은 백준이에게.. 최대 이익 선물해 주기

예전에 풀다가 대차게 틀렸던 문제였다.
분명 그때 풀이 보고 다음에 만나면 짓밟아 주겠다고 생각했는데 오늘 보니 또 새롭네요

---

생각하기

dp 냄새가 납니다.
백준이가 벌 수 있는 최대의 돈.. 뭔가 이전 최댓값과 비교해서 현재값이 더 크면 그게 정답이 될 것 같은 느낌이 들었어요.

i번째 날 작업이 걸리는 시간이 n인 경우, i+n날 이후 모든 날의 이익은 최소 i번째 날의 이익이라는 것을 깨닫는 게 중요하다.

---

🍳 전체 소스 코드

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

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

        System.out.println(total[n+1]);
    }
}

백문이 불여일견

• dp: 날짜별 작업 시간 & 이익 저장
• total 날짜별 누적 최대 이익 저장

현재 날짜에서 작업시간을 더한 날을 next라고 칭했을 때,
next 값이 퇴사날 이전인 경우 계산을 시작한다.

• 현재 날짜까지 최대 이익 (total[i]) +
  현재 날짜를 선택함으로써 얻을 수 있는 이익 (dp[i][1])

• next에 누적된 이익 (total[next])

위 두 개의 값 중 더 큰 값을 total[next]에 저장한다.

숫자에 빨간 표시한 부분이 최대 이익이 갱신된 경우 다.
위와 같은 로직으로 계산이 이루어진다고 생각하면 된다.

우리는 배열을 만들 때, 퇴사날인 8일의 공간을 만들어 줘서 total[8]에 최대이익을 저장하면 된다. 나는 이 방법을 반복문 내에, i+n일 이후부터 퇴사날까지 반복문을 하나 더 두어서 최대 이익을 저장할 수 있게 했다.

이중 반복문이기에 내 풀이는 효율적이진 않다.
반복문을 돌리지 않고 풀 수 있는 방법이 있지만, 문제를 풀고 나서 깨달았다.

for(int i=1;i<=n;i++){
	int time = dp[i][0]+i;
    if(time <= n+1){
    	total[time] =  Math.max(total[time], dp[i][1]+total[i]);
	}
	total[i+1]=Math.max(total[i],total[i+1]);
}

이중 반복문이 아닌, 현재 날짜의 다음 날짜의 최대 이익을 비교해서 다음 날짜의 최대이익을 갱신하면 된다.

그렇게 되면, 우리는 퇴사날까지 우리가 구한 최대 이익을 들고 갈 수가 있다.

---

✨ 결과

음. 혼자 푼 거 꽤괜
시간 단축만 하면 될 거 같다