[BOJ][🟡5][백준#02056] 작업

문제 출처

BAEKJOON Online Judge #2056

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다) 모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

입력

첫째 줄에 N이 주어진다. 두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, …, N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.

출력

첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.

예제

입력

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

출력

23

My Sol

def calc_time(n):
    global time, dp, first
    if dp[n]: return dp[n]

    if not first[n]:
        dp[n] = time[n]
        return dp[n]

    maxx = 0
    while first[n]:
        nn = first[n].pop()
        ret = calc_time(nn)
        if maxx < ret:
            maxx = ret

    dp[n] = time[n] + maxx
    return dp[n]


N = int(input())
dp = [0]*(N+1)
time = [0]*(N+1)
first = [set() for _ in range(N+1)]
for i in range(1, N+1):
    t, n, *arr = map(int, input().split())
    time[i] = t
    first[i] = set(arr)

for i in range(1, N+1):
    dp[i] = calc_time(i)

print(max(dp))

DP를 사용하는 문제였다. 여러 번 계산되어야 하는 작업을 메모이제이션하여 사용하는 방식이다.

1. 메모이제이션으로 기록하는 DP 배열을 0으로 초기화한다.
2. 입력을 처리한다.
3. 만약 dp 배열의 특정 인덱스가 값이 추가된다면 이미 해당 인덱스까지의 작업은 선행 작업을 마친 뒤의 최소 시간을 의미한다.
4. 선행 작업의 모든 dp 배열을 채우는 방식으로 선행 작업의 시간들을 가져온 뒤, 선행작업들의 작업시간의 최댓값과 현재 시간을 더한 값을 현재 인덱스의 dp에 저장한다.
5. 이를 반복하며 모든 dp 배열을 채운다.
6. dp 배열의 최댓값을 출력한다.

결과

맞았습니다!!