문제

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

실버 III

코드 (Java)

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

class Main {
    private static int N;
    private static int[][] schedules;
    private static int[] maxRewards; //maximum reward that can be obtained starting at this date.
    private static final int DAYS = 0, REWARD = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        schedules = new int[N+1][2];
        maxRewards = new int[N+1];

        //obtain data.
        for (int i = 1; i <= N; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; ++j) {
                schedules[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //since N is maximum of 15...
        //we calculate backward starting at day N.
        for (int i = N; i >= 1; --i) {
            maxReward(i);
            //bw.write(maxRewards[i] + "\n");
        }

        int answer = 0;
        for (int i = 1; i <= N; ++i) {
            answer = Math.max(answer, maxRewards[i]);
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    public static void maxReward(int day) {
        int maxReward = 0;
        int maxLeftOver = 0;

        //can't finish in time.
        if (schedules[day][DAYS] + (day - 1) > N) return;

        //accept this appointment.
        maxReward += schedules[day][REWARD];

        //backtrack(?) -> bottom-up dp.
        for (int i = day + schedules[day][DAYS]; i <= N; ++i) {
            maxLeftOver = Math.max(maxRewards[i], maxLeftOver);
        }

        //maximum obtained like below.
        maxRewards[day] = maxLeftOver + maxReward;
    }
}

풀이

• top-down dp 활용.

• 요즘 드는 생각인데, 난 참 dp에 약하다. 이거 푸는데 무슨 25분이나 걸리냐.

• 그리고 백트래킹/dp 개념은 알고 있으면서 상향식/하향식 dp도 제대로 모르고(...) 정작 저건 또 백트래킹인줄 알고(...) 그래서 이 글을 썼다.

• 이론과 관련해서는 이 글을 참고하도록 하고... 이 풀이는 bottom-up, 즉 상향식 풀이인데 iteration만 반대로 한 것이다. iteration을 순차적으로 하는 방법도 있는데 이 글 참고

• 보통 우리가 dp라고 할 때 일컫는 것은 bottom-up, 즉 상향식이다. 왜냐하면 시간 효율이 좋기 때문. 재귀 호출이 없기 때문에 그렇다.

• 백트래킹은 완전 다른 내용이니 참고