1005번 ACM Craft

https://www.acmicpc.net/problem/1005

---

아이디어

처음에 고민했던 건 병렬로 동시에 지을 수 있다는 점이다. 그래서 어떻게 해야할지 몰랐었는데 그냥 DP로 누적하면 된다.

for i in graph[a]: # a와 연결되어 있는 건물들
	dp[i] = max(dp[i], dp[a]+D[i-1]) 

a와 연결된 건물들로 for문을 돌면서 원래 자기 자신이 큰 지, 이전에 누적된게 큰지만 비교하면 된다. 더 큰 걸로 선택해야 한다!

---

코드

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, K = map(int, input().split()) # 건물 개수, 규칙 개수
    D = list(map(int, input().split())) # Delay
    graph = [[] for _ in range(N+1)]
    degree = [0]*(N+1) # 연결 되어 있는 건물 확인 리스트
    for i in range(K):
        X, Y = map(int, input().split()) # X 다음에 Y 지어야함
        graph[X].append(Y)
        degree[Y] += 1 # 차수 증가
    W = int(input()) # 건설해야 할 건물 번호

    dp = [0]*(N+1)
    # 위상정렬
    queue = deque()
    for i in range(1, N+1):
        if degree[i] == 0: # 진입차수가 0이면
            queue.append(i)
            dp[i] = D[i-1] # i번째 건물의 딜레이는 D[i-1] 이유: D는 입력으로 받아서 인덱스 0이 1번 건물

    while queue:
        a = queue.popleft()
        for i in graph[a]: # a와 연결되어 있는 건물들
            dp[i] = max(dp[i], dp[a]+D[i-1]) # 원래 자기자신이 큰 지, 이전에 누적된 게 큰 지
            degree[i] -= 1 # 차수 1개 끊기
            if degree[i] == 0: # 차수가 0이면
                queue.append(i) # 진입차수가 0이므로 append
    print(dp[W]) # W 건물 짓는데 소요시간