아이디어

• 관계를 그래프(인접리스트)로 가지고 N번 부품(완제품)부터 해체해보자.
• 이때, 다른 상위 제품이 남아있을 때 해체를 해버리면 상위 제품을 해체할 때 다시 재해체해야하므로, 상위 제품이 남아있지 않은 부품만 해체하자.
• 이는 그래프의 입력차수가 0인지 아닌지를 보면 된다. 즉, 위상정렬을 이용해 풀 수 있다는 뜻이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, M, X, Y, K;
	static List<List<Integer>> graph = new ArrayList<>();
	static int[][] ingred;
	
	static int[] parts, indeg;
	static Queue<Integer> q = new ArrayDeque<Integer>();
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		M = Integer.parseInt(rd.readLine());
		
		ingred = new int[N+1][N+1];
		
		for (int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		indeg = new int[N+1];
		
		for (int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			X = Integer.parseInt(tk.nextToken());
			Y = Integer.parseInt(tk.nextToken());
			K = Integer.parseInt(tk.nextToken());
			
			graph.get(X).add(Y);
			ingred[X][Y] = K;
			indeg[Y]++;
		}
		parts = new int[N+1];
		parts[N] = 1;
		
		q.offer(N);
		while (!q.isEmpty()) {
			int v = q.poll();

			for (int i=1; i<=N; i++)
				parts[i] += ingred[v][i] * parts[v];
			parts[v] = 0;
			
			for (int n: graph.get(v)) {
				if (--indeg[n] == 0 && !graph.get(n).isEmpty()) {
					q.offer(n);
				}
			}
		}
		
		for (int i=1; i<=N; i++) {
			if (graph.get(i).isEmpty()) {	// basic
				sb.append(i).append(' ').append(parts[i]).append('\n');
			}
		}
		
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 14100 KB
• 시간: 120 ms

리뷰

• 굳이 참조 관계와 필요 개수 그래프를 나눌 필요는 없었지만, 구조적으로는 이게 더 간단했다.
• 이 문제를 DP로 풀려면... 일종의 벡터를 만들어서 합하는 식으로 되나?