[백준] 퇴사 14501 (Java)

문제 링크

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

나의 풀이

주의점

• n + 1일에 퇴사를 하기 때문에 상담이 n+1 일에 끝나는 경우까지 고려해야 합니다.

처음 접근

• 1일부터 n일까지 해당 날짜의 상담을 진행하는 경우 안하는 경우를 고려해서 점화식을 세우려고 시도해봤습니다.
• 만약, 1일차 상담에 이틀이 필요할 때 3일차 상담을 진행하는 경우의 점화식을 어떻게 세울지 고민하다 결국 해결하지 못하고 구글링을 했습니다.

구글링 결과

1일 부터 시작하는 것이 마지막 n일부터 시작해서 dp테이블을 갱신합니다.

• n=7
• 7일차 상담은 이틀이 필요하기 때문에 7 + 2 > n+1 이므로, 상담을 진행할 수 없습니다.
• 2일차 상담의 경우 5일이 필요하기 때문에 max(20 + dp[5], dp[i+1])이 됩니다. 
  • 첫 번째 인자가 2일차 상담을 진행하는 경우
  • 두 번째 인자가 2일차 상담을 진행하지 않는 경우입니다.

1일차	2일차	3일차	4일차	5일차	6일차	7일차
3	5	1	1	2	4	2
10	20	10	20	15	40	200

Code

package dp.boj_14501;

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


public class Main {
    static int[] dp;
    static int[] costs;
    static int[] pay;
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        dp = new int[n + 2];
        costs = new int[n + 1];
        pay = new int[n + 1];


        for (int i = 1; i < n+1; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            costs[i] = cost;
            pay[i] = p;
        }


        for (int i = n; i >= 0; i--) {
            if (costs[i] + i > n+1) {
                //상담 진행 불가
                dp[i] = dp[i + 1];
            }
            else{
                dp[i] = Math.max(pay[i] + dp[i + costs[i]], dp[i + 1]);
            }
        }
        System.out.println(dp[0]);
    }
}

Git

https://github.com/youngh0/java-algorithm/blob/master/algorithm/src/main/java/dp/boj_14501/Main.java