[BOJ 14501] 퇴사 - JAVA, Silver3

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

14501번: 퇴사

사용한 알고리즘 : DP

 

풀이전략

DP 문제를 풀 때, 보통 맨 처음 입력으로 주어진 값을 시작으로 반복성을 찾아낸다

하지만, 이 문제에서는 입력의 맨 뒤부터 반복성을 찾아야 풀 수 있는 문제이다.

 

위 표는 문제에서 주어진 1번 예제 입력을 대입했을 경우, 얻을 수 있는 최대 수익을 나태는 표이다.

d[i]는 i~N일 사이에 얻을 수 있는 최대 수익을 뜻한다.

(예로 d[3]은 3~7일 사이에 얻을 수 있는 최대 수익을 뜻함)

 

이 문제는 입력의 맨 뒤부터 시작하여 반복성을 찾아야 한다고 했는데, 아래와 같은 반복성을 띈다.

 

7일 : T7 = 2로 (7+T7 = 9), 업무 마지막날인 7일까지 작업을 마칠 수 없으므로 d[7]=0

6일 : T6 = 4로 (6+T6 = 10), 업무 마지막날인 7일까지 작업을 마칠 수 없으므로 d[6]=0

5일 : T5 = 2로 (5+T5 = 7), 업무 마지막날인 7일까지 작업을 마칠 수 있으므로 d[5]=P5=15

4일 : T4 = 1로 (4+T4 = 5), 업무 마지막날인 7일까지 작업을 마칠 수 있으므로

         d[4]=Math.max(P4+d[4+T4],d[4+1])=Math.max(20+15,15)=35

3일: T3 = 1로 (3+T3 = 4), 업무 마지막날인 7일까지 작업을 마칠 수 있으므로

         d[3]=Math.max(P3+d[3+T3],d[3+1])=Math.max(10+35,35)=45

2일 : T2 = 5로 (2+T2 = 7), 업무 마지막날인 7일까지 작업을 마칠 수 있으므로

         d[2]=Math.max(P2+d[2+T2],d[2+1])=Math.max(20+0,45)=45

1일 : T1 = 3으로 (1+T1 = 4), 업무 마지막날인 7일까지 작업을 마칠 수 있으므로

         d[1]=Math.max(P1+d[1+T1],d[1+1])=Math.max(10+35,45)=45

 

즉,   i+Ti>7이면 d[i]=d[i+1]이고

       i+Ti<=7 이면 d[i]=Math.max(Pi+d[i+Ti],d[i+1]) 이다.   (i는 날짜)

 

나는 d를 선언할 때, int d[] = new int[N+2]로 선언하여  d[0]과 d[N+1]을 0으로 채웠다.

이유는 i번째 날에 얻을 수 있는 최대 수익을 d[i]로 나타내기 위해 d[0]을 쓰지 않지만 정의했고,

d[N+1]은 d[i]=Math.max(Pi+d[i+Ti],d[i+1])에서, Pi+d[i+Ti]-1=N인 경우 d[i+Ti]가 d[N+1]이 되어

OutOfBounds 에러가 발생하지 않도록 하기 위해 정의했다.

 

제출코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int T[] = new int[N+1];
        int P[] = new int[N+1];
        for(int i=1;i<=N;++i){
            st = new StringTokenizer(br.readLine());
            T[i]=Integer.parseInt(st.nextToken());
            P[i]=Integer.parseInt(st.nextToken());
        }
        int d[] = new int[N+2];
        if(T[N]==1) d[N]=P[N];
        for(int i=N-1;i>0;--i){
            if(i+T[i]-1>N) d[i]=d[i+1];
            else d[i]=Math.max(P[i]+d[i+T[i]],d[i+1]);
        }

        bw.write(d[1]+"\n");
        bw.flush();
        bw.close();
    }
}