문제 링크

ACM craft

문제 설명

매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.

위의 예제에서 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.
따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.
백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

문제 풀이

시도 1

위상정렬이 뭔지 모르니까 난,,^^ 문제 읽자마자 탑다운을 이용한 dp로 풀면 되겠다는 생각이 들었다.

1. 상태 정의

$dp[i]$ : i번째 건물을 짓는데에 총 소요되는 시간
$pre[i]$ : i번째 건물을 짓기 직전에 지어져야 하는 건물
$time[i]$ : i번째 건물자체를 짓는데에 소요되는 시간

$pre[i] = [i_1, i_2, ..., i_n]$이라 했을때,
$dp[i] = max(dp[i_1], dp[i_2],..., dp[i_n]) + time[i]$

2. 코드

import sys

input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(100000)

def get_time(building):
    #이미 계산한 적 있으면
    if dp[building] != 0:
        return dp[building]
    else:
        tmp = 0
        # 맨 처음 지어야하는 빌딩
        if building in pre.keys():
            for i in pre[building]:
                tmp = max(tmp, get_time(i))
        dp[building] = tmp + time[building]
        return dp[building]

tc = int(input())
answer = []
for i in range(tc):
    N, K = map(int, input().split())
    time = [0] + list(map(int, input().split()))
    pre = {}    #건물 i 직전에 지어야 하는 건물 저장
    for j in range(N+1):
        pre[j] = []
    
    for j in range(K):
        before, after = map(int, input().split())
        pre[after].append(before)
    W = int(input())

    dp = [0]*(N+1)
    # 건물 i를 짓는데 걸리는 시간 = max(직전에 지어야 하는 건물 소요시간) + 지금건물 짓는 소요시간
    answer.append(get_time(W))

for a in answer:
    print(str(a)+'\n')

Umm,,,,,, ㅎㅎ,,,,
dict에서 매번 in이나 not in으로 찾는데에 소요되는 시간이 길거같아서 각각의 건물을 짓기 직전에 지어져야 하는 건물을 저장하는 pre를 dict에서 list로도 바꿔보고,, print도 sys.stdout.write로 바꿔보고 나름 최적화를 시켜보려고 했는데 66%에서 계속 시간초과가 났다 ^_ㅠ,,,,,,,,,

시도 2

위상정렬을 사용한다.
위상정렬의 기본 개념은 동빈나님의 27강-위상정렬을 참고해서 여기에 정리했습니다~

import sys
from collections import deque

input = sys.stdin.readline

def topology_sort():
    Q = deque()
    
    for i in range(1, N+1):
        if indegree[i] == 0:
            Q.append(i)
            dp[i] = time[i-1]

    while Q:
        now = Q.popleft()

        for i in graph[now]:
            indegree[i] -= 1
            dp[i] = max(dp[now]+time[i-1], dp[i])              

            if indegree[i] == 0:
                Q.append(i)
    answer.append(dp[W])

tc = int(input())
answer = []

for _ in range(tc):

    N, K = map(int, input().split())
    time = list(map(int, input().split()))
    
    indegree = [0] * (N+1)
    graph = [[] for i in range(N+1)]
    dp = [0] * (N+1)
        
    for _ in range(K):
        before, after = map(int, input().split())
        graph[before].append(after)
        indegree[after] += 1
    W = int(input())
    topology_sort()
    
for ans in answer:
    print(ans)

음 어렵군,,