2025-동계 모각코 3회차 회고

백준의 문제를 제일 낮은 1000번부터 번호순대로 풀기 시작하면, 내가 오늘 푼 1005번 문제에서 막히게 된다는 이야기가 있다.

내 문제 해석은 다음과 같다.

먼저, 예시에 따르면 결국 마지막에 지어지는 건물을 기준으로 잡아야 한다고 생각했다.

그러면 그 건물 n번을 짓는 데에 드는 시간은 입력에서 받는 'n번의 시간' + 'n번 건물의 선행 조건으로 주어지는 건물들의 시간 중 가장 큰 값'일 것이다. 여기서 DP 태그의 냄새가 강하게 났다. 다만, 이렇게 진행하면 평소에 풀던 문제들과는 다른 역방향으로 DP를 수행하게 된다.

그렇다면, 마지막에 지어지는 건물은 어떻게 추려낼 수 있는가?

나는 찾아내지 못했다. 예시 입력의 경우는 번호가 가장 큰 N번이 제일 마지막에 지어지는 듯 했으나, 입력 조건에 따르면 번호에 주어진 규칙은 없어서, 건물 번호들은 뒤집은 형태도 가능하다고 판단했다.

그럼 어떤 건물을 기준으로 삼아야 할까?

소모 시간이 가장 큰 건물을 기준으로 삼아보려고 했으나, 점화식이 꼬여 실패했다.

'그럼 그냥 정방향 DP로 승부를 봐야 하겠구나'라는 생각으로, 선행 조건이 없는 건물들을 먼저 탐색하기로 했다.

1005번 문제 알고리즘 분류

정보를 찾으며 '위상 정렬'이라는 단어의 의미를 알게 되었고, 단어는 몰랐으나 모든 태그들은 맞출 수 있었다.

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

public class Main {
    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 tc = 0; tc < t; tc++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            long[] time = new long[n + 1];
            long[] dp = new long[n + 1];
            int[] indeg = new int[n + 1];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                time[i] = Long.parseLong(st.nextToken());
                dp[i] = time[i];
            }

            ArrayList<Integer>[] graph = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

            for (int i = 0; i < k; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                graph[from].add(to);
                indeg[to]++;
            }

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

            ArrayDeque<Integer> q = new ArrayDeque<>();
            for (int i = 1; i <= n; i++) {
                if (indeg[i] == 0) q.add(i);
            }

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

                for (int v : graph[u]) {
                    dp[v] = Math.max(dp[v], dp[u] + time[v]);
                    indeg[v]--;
                    if (indeg[v] == 0) q.add(v);
                }
            }

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

        System.out.print(sb);
    }
}

다만, 구현은 힘들어 결국 LLM의 손을 조금 빌리게 되었다.

솔브닥의 클래스 별 문제를 따라가다 보면 새로운 알고리즘을 배울 때 코드를 짜기가 힘든 경향이 있는데, 차차 익숙해지겠지. 

---

2025.12.20 - [PS/알고리즘과 자료구조] - [JAVA] 재귀와 DP(동적 계획법)

[JAVA] 재귀와 DP(동적 계획법)

생각보다 손이 많이 가는 일이구나, 이거.