[Algo] 백준 15486 퇴사 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/15486

메모리 : 402864KB

시간 : 1056ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int start, cost;

        Node(int start, int cost) {
            this.start = start;
            this.cost = cost;
        }
    }

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<List<Node>> table = new ArrayList<>();
        StringTokenizer st;
        for (int i = 0; i <= N; i++) {
            table.add(new ArrayList<>());
        }
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            if (end + i > N)
                continue;
            table.get(end + i).add(new Node(i, cost));
        }
        int[] dp = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            for (Node n : table.get(i)) {
                dp[i] = Math.max(dp[n.start] + n.cost, dp[i]);
            }
            dp[i] = Math.max(dp[i], dp[i - 1]);
        }
        System.out.println(dp[N]);
    }
}

풀이

어려워 하는 DP다ㅜ 거스름돈 만들기와 같은 문제로 보고 접근했더니 결국 N일에 일을 하는 것이 최선인지, 안하는 것이 최선인지 판단해야 한다고 생각했다. 그래서 일이 끝나는 시점, 즉 돈을 받을 수 있는 시점에서 회귀해 이 일을 하는 것이 최선이었는지 계산해봤다. 근데 너무 느려!

친구의 풀이를 훔쳐본 결과 max라는 변수를 놓고 N일에 일을 하지 않은 경우 와 N일에 일을 한 경우 얻을 수 있는 소득 + max를 비교하면 간단했다.