백준 [2637] 장난감 조립(JAVA)

2차원 dp 테이블을 이용했다.

완성품 즉, 엔드 포인트가 N이라고 했으니

이 N을 기준으로 각 부품들의 개수를 구해주면 된다.

 

각 중간 부품들과 완제부품들에 기본 부품이 몇 개나 필요한지 모두 적어보면 감이 잡힐 것이다.

 

코드

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

class Main {

    static int N, M;
    static int[] count;
    static int[][] dp;
    static ArrayList<Node>[] nodes;
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        dp = new int[N + 1][N + 1];
        count = new int[N + 1];
        nodes = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++)
            nodes[i] = new ArrayList<>();

        int e, s, c;
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            e = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            nodes[s].add(new Node(e, c));
            count[e]++;
        }
    }

    private static void solve() {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if(count[i] == 0) {
                dp[i][i] = 1;
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int here = q.poll();
            for (Node there : nodes[here]) {
                for (int i = 1; i <= N; i++)
                    dp[there.index][i] += there.c * dp[here][i];
                if(--count[there.index] == 0)
                    q.add(there.index);
            }
        }
        for (int i = 1; i <= N; i++) {
            if(dp[N][i] > 0)
                answer.append(i + " " + dp[N][i] + "\n");
        }
    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.flush();
    }
}

class Node {
    int index, c;

    public Node(int index, int c) {
        this.index = index;
        this.c = c;
    }
}

 

예시 1을 도식화하면 다음과 같다.

예시 1

 

정석적으로 count가 0인 정점에서 시작해

중간에 마주치는 정점들의 count를 1씩 깎으며 계산해 나가려 하지만 문제가 발생한다.

 

count를 확인하면 부품 5, 6, 7은 각각 2, 3, 3을 가지는데

이는 4개의 기본부품들에서부터 계산해 나가기엔 부족한 수치다.

7까지 도달한다 했을 때 루트는

1 -> 5 -> 7

2 -> 5 -> 7

1 -> 5 -> 6 -> 7

2 -> 5 -> 6 -> 7

3 -> 6 -> 7

4 -> 6 -> 7

4 -> 7

이기 때문에 일반적인 접근으로는 해결할 수 없다.

그래서 각 기본 부품들에 대해 BFS돌리면 될 줄 알았는데 메모리 초과가 났다.

 

그렇다면 다른 방식으로 생각해야 하는데 내가 생각했던 부분은 다음과 같다.

완제품 7은 아무튼 부품 4, 5, 6을 통해 생성된다.

부품 4, 5, 6들이 모두 완성된 상태여야 7을 만들 수 있고,

이는 부품 4, 5, 6들이 중간 결과를 의미한다 볼 수 있다.

즉, dp 쓰라는 얘기다.

 

완제품과 각 중간제품들이 만들어지는데 필요한 기본 부품을 정리하면 다음과 같다.

 

 

이제, 현재 부품들을 구성하는 기본 부품들의 수 * 간선의 가중치를

다음 단계의 기본 부품들의 수에 합산하면 된다.

 

예를 들어, 중간 부품 5은 중간 부품 6과 완제품 7에서 필요하니

중간 부품 6은 중간 부품 5가 2개 필요하니

[6][1] += [5][1] * 2

[6][2] += [5][2] * 2

처럼 되고,

완제품 7은 중간 부품 5가 2개 필요하니

[7][1] += [5][1] * 2

[7][2] += [5][2] * 2

가 된다.

 

점화식을 만들면 다음과 같다.

dp[대상 부품 Index][기본 부품 Index] += 간선의 가중치 * dp[중간 부품 Index][기본 부품 Index]