BOJ 14501 - 퇴사

14501번: 퇴사 (acmicpc.net)

 

N일 동안 상담을 진행한다.

각 날 별로 걸리는 기간(T)과 상담을 했을 때 받을 수 있는 금액(P)으로 이루어져 있다

예를 들어 1일에 T = 3이고 P = 10이라고 해보자.

1일에 잡혀있는 상담은 총 3일이 걸리며 상담 시 받을 수 있는 금액은 10이다.

T가 1보다 클 수 있기 때문에 모든 상담을 할 수는 없다. 예를 들어 1일 상담을 하기로 결정하면 2, 3일은 상담을 할 수 없다.

또한 N + 1일에는 회사에 없기 때문에 그것도 고려해서 상담을 결정해야 한다.

상담 일정을 적절히 골라 최대 수익을 구하라.

 

일단 확실한 건 마지막 N일의 상담은 T가 1이 아니면 선택할 수 없다.

해야 할 일은 그날 상담을 할지 말지를 결정해야 한다.

우선은 완전탐색을 고려할 수 있다. 그런데 이 경우 중복된 계산이 빈번하게 등장한다.

이 중복 된 계산은 저장해 두면 속도 향상이 될 것이다.

결국에는 DP 문제이다. 최대 수익을 저장하면 될 것이다.

그런데 이전의 선택이 다음의 선택에 영향을 주고 있다.

그렇다면 뒤에서부터 접근하면 날짜 결정 이후의 결과에 영향을 주지 않을 것이다.

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

public class Main {

    static FastReader scan = new FastReader();
    static int N;
    static Consult[] consults;

    static class Consult {
        int T;
        int P;

        public Consult(int day, int price) {
            this.T = day;
            this.P = price;
        }
    }

    static void input() {
        N = scan.nextInt();
        consults = new Consult[N + 1];
        for (int i = 1; i <= N; i++) {
            int day = scan.nextInt();
            int price = scan.nextInt();

            consults[i] = new Consult(day, price);
        }
    }

    public static void main(String[] args) {
        input();

        int[] DP = new int[N + 2];

        for (int day = N; day >= 1; day--) {
            if (day + consults[day].T <= N + 1) {
                // day의 상담이 가능한 경우 -> 현재 상담 + 최대 수익 vs 현재 상담 x
                DP[day] = Math.max(consults[day].P + DP[day + consults[day].T], DP[day + 1]);
            } else {
                DP[day] = DP[day + 1];
            }
        }

        System.out.println(DP[1]);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException{
            br = new BufferedReader(new FileReader(s));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}