[백준] 퇴사 (!) (14501번 JAVA) / DP

[백준] 퇴사 (!) (14501번 JAVA) / DP

---

[접근 방법]

 

* 물리적으로 불가능한 것 (퇴사 후엔 상담이 불가능) 을 제외한다.

(N = 7인 경우, 7일차에 2일이 걸리는 상담을 할 수 없다.)

 

역방향으로 DP를 도출한다. N -> 1 순으로,

for (i = N -> 1 까지 i--){
	
    // 물리적으로 불가능한 것 제외
    if ( 현재 일자(i) + 상담에 드는 기간(T[i]) > N + 1 ){
    	DP[i] = DP[i+1];
    }
    else {
    	i 날짜의 일을 하는 경우 => DP[i + T[i]] + P[i]
        i 날짜의 일을 하지 않는 경우 => DP[i+1]
        
        중 최댓값 구하기
    }
}

 

---

[JAVA 코드]

// 14501 - 퇴사
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 노동기간 : N (1 ≤ N ≤ 15)
        int N = Integer.parseInt(br.readLine());
        // 상담기간
        int[] T = new int[N+1];
        // 상담수익
        int[] P = new int[N+1];
        int[] DP = new int[N+2];

        for(int i=1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=N; i>0; i--){

            /*
            EX) N = 7인 경우,
            7일차(i)에 2일(T[7] = 2)이 소요되는 일을 시작할 수 없음.
            */
            if (i + T[i] > N + 1){
                DP[i] = DP[i+1];
            }
            else {
                DP[i] = Math.max(DP[i+1], DP[i + T[i]] + P[i]);
            }
        }


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

---

[Rewind]

1. 어려웠던 점

 

- DP 점화식을 구성하지 못하였음.

- DP 배열을 어떠한 방식으로 사용해야 하는지 생각해내지 못함

 

2. 알게된 점

 

- DP를 역방향으로 구성하는 방법으로 해결한다는 점

(DP[i-2] , DP[i-1] 등 을 이용하여 DP[i]를 도출하는 방법이 아닌,

DP[N] 부터 시작하여, DP[1]까지 도출하는 것)

 

- 물리적으로 불가능한 경우를 제거하는 방식

(N = 7 인 경우,

7일차에 2일 이상이 드는 상담을 시작할 수 없음 => 해당 경우를 고려하지 않음.)

 

3. 개선 방향

 

- 더 많은 DP 문제에 노출되어야 한다.

- 다양한 유형의 점화식 도출방법을 이용한다.