DP 문제를 놓치지 않아요

이전에 DP 알고리즘을 정리한 적이 있는데, 까먹은 건지 DP인걸 캐치하지 못했다.
반성 겸, 정리 겸 DP를 다시 한번 정리하려고 한다.

1005번 ACM Craft가 DP였던 이유

가장 먼저, 이 글을 정리하게 된 계기를 정리해보자.

문제 설명

• 선행 조건에 따라 건물 짓는 순서가 결정 (DAG)
• 어떤 건물을 짓는데 걸리는 시간을 계산해야한다. ( → 이 부분이 DP)

이 문제를 풀면서 나는 여기까지 도달했다.

내 아이디어

1 -> 3      -> 4 
  -> 2 -> 5 -> 4
의문점1) 3,2 단계에서는 2의 시간만 필요한데, 이걸 이 시점에 알 수 있을까? 

1 -> 3 -> 4 -> 5
2 -> 6 -> 7 
의문점2) 7의 관점에서는 1,3,4,5의 시간은 필요없는데 이걸 어떻게 알 수 있을까? 

그리디일까? ❌ 

• 3의 시간이 더 짧기 때문에 2가 아니라 3을 선택하면 답이 틀린다.

어떤 순간의 최적인 답이 최종 정답으로 이어지지 않는다.

👉 따라서 특정 건물을 짓는데 걸리는 시간을 계산하기 위해서는 각 과정에 걸리는 값을 어딘가에 저장 후(메모제이션) 나중에 활용해야한다.  

DP란

부분 문제 결과를 저장하고 재활용한다.

👉 겹치는 하위 문제 + 최적 부분 구조 + 메모이제이션(또는 테이블링)

• 해당 문제의 구조가 하위 문제를 활용해서 (비교 해서) 결정된다.
• 과거 선택을 전부 기억하고 있어야 답을 구할 수 있다.

DP 문제 특징

• 서로 다른 경로가 “합쳐져서 경쟁함”
• 과거 선택을 전부 기억하지 않으면 답 못 구함
• 최적해가 여러 하위 문제들의 비교 결과로 나옴
• “누적값 최대/최소/경우의 수”가 등장함

키워드 : 최소 시간, 최대 이득, 경로 수, 누적, 겹치는 부분 문제

결국 1005번 문제는

• 여러 선행 경로 중 가장 오래 걸리는 경로를 선택해야한다.
• 지금 당장 결정할 수 없고, 계속 갱신하다가 마지막에 결정해야한다.
• 누적 시간이 등장한다.

1005 ACM Craft

dp 점화식

a -> b : dp[b] = max(dp[a]+time[b],dp[b])

풀이

• 진입차수가 0인 노드를 저장한 큐에서 꺼내기
  • 결과에 넣기 (노드 : a)
  • 관련 경로 차수 - - ; dp[관련 경로] = max(dp[a]+time[관련 경로], dp[관련 경로])
  • 차수 0이 된 노드 큐에 넣기
• 큐가 빌 때까지 계산

정답 코드

package day11_GraphDeepening;

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

public class BOJ1005ACMCraft {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int[] degree = new int[n + 1];
            int[] time = new int[n + 1];
            int[] dp = new int[n + 1];
            Queue<Integer> q = new ArrayDeque<>();

            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n + 1; j++) {
                time[j] = Integer.parseInt(st.nextToken());
            }

            List<Integer>[] graph = new ArrayList[n + 1];
            for(int j = 1; j < n + 1; j++) {
                graph[j] = new ArrayList<>();
            }

            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                graph[a].add(b);
                degree[b]++;
            }

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

            for (int j = 1; j < n + 1; j++) {
                if (degree[j] == 0) {
                    q.offer(j); //i로 함
                    dp[j] = time[j];
                }
            }

            while (!q.isEmpty()) {
                int node = q.poll();

                for (int k : graph[node]) {
                    degree[k]--;
                    dp[k] = Math.max(dp[k], time[k] + dp[node]);
                    if (degree[k] == 0) {
                        q.offer(k); //node로 해놓음
                    }
                }
            }

            sb.append(dp[w]).append("\n");
        }
        System.out.println(sb);

    }

}