백준 1005 ACM Craft | 파이썬, DP

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

1005번: ACM Craft

 

건물을 짓는 데 걸리는 시간(D)와 건물의 건설 순서를 X, Y형태로 알려주고 W번째 건물을 짓는데 걸리는 시간을 출력하는 문제

 

건물의 수는 5이고 건설 순서 개수는 4이다.

건물물을 짓는데 걸리는 시간(D)는 D[1] = 1, D[2] = 2, D[3] = 3, D[4] = 4, D[5] = 5이다.

건설 순서가 [1, 2], [4, 2], [2, 3], [5, 3]이고 3번째 건물물을 짓기위해 필요한 총 시간을 구해야 한다.

3번째 건물의 건설 총시간을 구하기 위해서는 2, 5번째 건물의 건설 총시간을 구해야한다.

2번째 건물의 건설 시간을 구하기 위해서는 1, 4번째 건물의 건설시간을 구해야한다.

5번째 건물은 먼저 지어져야하는 건물이 없으므로 건설 총시간은 5이다.

1, 4번째 건물은 먼저 지어져야하는 건물이 없으므로 건물을 짓는데 걸리는 시간은 각각 1, 4이다.

2번째 건물의 건설 총시간은 1, 4번째 건물의 건설 총시간 중 최대값에 2번째 건물의 건설 시간을 더한 값이다.

(1, 4번째 건물이 모두 완성되어야 2번째 건물을 지을 수 있으므로 최대값을 선택한다.)

그러므로 2번째 건물의 건설 총시간은 4 + 2이다.

3번째 건물의 건설 총시간은 2, 5번째 건물의 건설 총시간 중 최대값에 3번째 건물의 건설 시간을 더한 값이다.

그러므로 3번재 건물의 건설 총시간은 6 + 3이다. 

 

문제 풀이 과정을 보면 알겠지만 탑다운 방식의 dp를 사용해 문제를 해결할 수 있다.

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N, K = map(int, input().split()) # 건물 개수, 건설순서 개수
    D = [0] + list(map(int, input().split())) # 각 건물의 건설 시간
    PRE = [[] for _ in range(N+1)] # 먼저 지어져야 하는 건물을 저장하는 리스트
    for _ in range(K):
        X, Y = map(int, input().split())
        PRE[Y].append(X) # 먼저 지어져야하는 건물을 PRE에 저장
    W = int(input()) # 건설 총시간을 구해야하는 건물의 번호
    memory = [-1]*(N+1) # 메모이제이션을 위한 리스트

    def dp(n): # dp를 수행하는 함수
        if len(PRE[n]) == 0: # 먼저 지어져야하는 건물이 존재하지 않으면 
            return D[n]		 # 건물의 건설 시간을 반환

        if memory[n] >= 0:	 # 만약 기존에 건설 총시간을 구한 건물인 경우
            return memory[n] # 전에 구해놨던 건설 총시간 반환

        result = 0
        for i in PRE[n]:	 # 먼저 지어져야하는 건물을 순회
            result = max(result, dp(i)+D[n]) # 건설 총시간의 최대값 구하기

		# 구한 건설 총시간을 저장
        memory[n] = result
        return memory[n]

    print(dp(W))

 

처음에는 바텀업 방식을 사용했다. 근데 8%에서 계속 틀렸습니다를 받았다.

바텀업 방식은 1번째 부터 N번째까지의 건설 총시간을 구하는데 건설 순서를 어떤 식으로 순회하냐에 따라 답이 계속 바꼈다.

그래서 재귀함수를 사용한 탑다운 방식으로 풀었다.

W와 관련된 건물의 건설 총시간만 구하면 답을 얻을 수 있었다.

dp문제를 풀 때 바텀업으로 푸는게 안전?하고 빨라서 거기에 익숙해져있었나 보다.