[BOJ/JAVA] 14501번: 퇴사

14501번: 퇴사

14501번: 퇴사

키워드

N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 **최대한 많은 상담**을 하려고 한다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익

---

구현

상담을 완료하는데 걸리는 기간 배열, 상담을 했을 때 받을 수 있는 금액 배열을 입력받는다.

cache는 다음을 저장한다

• i-1일 부터 상담을 했을 때 얻을 수 있는 최대 수익
• DP의 구현
  1. 오늘 상담을 하는 경우
     • today+T[i-1] 날짜로 이동한다.
     • 받을 수 있는 금액 P[i-1]을 추가한다.
  2. 오늘 상담을 하지 않는 경우
     • today+1 날짜로 이동한다.

---

코드

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

public class java_14501 {
    static int N;

    static int timeList[];
    static int priceList[];

    static int cache[];

    // today부터 최대의 price를 버는 방법.
    static int dp(int today) {
        if (today == N) {
            return 0;
        }

        if (cache[today] != -1) {
            return cache[today];
        }

        cache[today] = 0;
        // 오늘 상담을 하는 경우
        if (today + timeList[today] <= N) {
            cache[today] = Math.max(cache[today], dp(today + timeList[today]) + priceList[today]);
        }
        // 오늘 상담을 하지 않는 경우
        cache[today] = Math.max(cache[today], dp(today + 1));

        return cache[today];
    }

    static int solve() {
        int result = 0;

        //
        cache = new int[N];
        Arrays.fill(cache, -1);

        result = dp(0);

        return result;
    }

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

        N = Integer.parseInt(br.readLine());

        timeList = new int[N];
        priceList = new int[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            timeList[i] = Integer.parseInt(st.nextToken());
            priceList[i] = Integer.parseInt(st.nextToken());
        }

        //
        int result = solve();

        System.out.println(result);

        br.close();
    }
}

---