[백준]JAVA - 14501번: 퇴사

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

14501번: 퇴사

풀이

이번 문제는 dp문제로 제목이 정말 맘에 든다.

퇴사까지 N일을 앞두고 있는 백준이에게 상담 시간과 금액이 주어졌다. 퇴사까지 최대한 많은 상담 비용을 찾는 문제이다.

이 문제에는 한 가지 경우의 수가 존재한다.

 

예제 1번을 살펴보면 다음과 같다.

1일에 예약된 상담의 시간은 3일이다. 즉, 4일차가 되는 날에 상담 비용 10을 얻을 수 있다.

2일에 예약된 상담의 시간은 5일이다. 즉, 7일차가 되는 날에 상담 비용 20을 얻을 수 있다.

3일에 예약된 상담의 시간은 1일이다. 즉, 4일차가 되는 날에 상담 비용 10을 얻을 수 있다.

4일..

5일..

6일에 예약된 상담의 시간은 4일이다. 퇴사일을 넘어가는 경우에는 상담 진행이 불가하다.

7일 또한 퇴사일이기 때문에 상담이 불가능하다.

 

1. 해당 일자 + 상담 시간이 퇴사일을 넘지 않는 경우

int next = i + T[i];
if (next < N+1) {
    dp[next] = Math.max(dp[next], dp[i] + P[i]);
}

	1일	2일	3일	4일	5일	6일	7일
상담 시간 T[i]	3	5	1	1	2	4	2
상담 비용 P[i]	10	20	10	20	15	40	200
dp[i]	0	0	0	10	30	0	45

표를 살펴보면 이상한 점을 발견할 수 있다. 필자도 이것을 생각 못하고 틀렸다.

위처럼 첫 번째 경우의 수만 생각하고 돌리면 2일, 3일, 6일의 금액이 0이다. 

말도 안되는 소리다. 5일에 벌 수 있는 최대 상담 비용이 30원인데 6일에 0원이라니...

 

이 문제는 간단하게 해결할 수 있다. 바로 이전 값을 가져오면 된다.

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

 

<최종코드>

import java.io.*;
import java.util.*;

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