Hanbit the Developer

[Python] 백준 2056번: 작업 본문

Algorithm/백준

[Python] 백준 2056번: 작업

hanbikan 2021. 8. 25. 11:02

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

 

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

 

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())
    costs = [0]*(N+1)

    for i in range(1, N+1):
        cur_input = list(map(int, input().split()))

        prev_max_time = 0
        for j in range(2, 2 + cur_input[1]):
            prev_max_time = max(prev_max_time, costs[cur_input[j]])

        costs[i] = prev_max_time + cur_input[0]

    print(max(costs))

 

먼저, DP의 역할을 하는 리스트인 costs[x]는 작업 X를 완료하기 위해 드는 시간이다.

그리고 문제의 조건에 의하면, 문제 N을 하기 위한 사전 작업들은 무조건 N 미만의 작업들이므로 for문을 1번만 돌려서 문제를 풀 수 있다.

 

반복문 내에서 입력을 받고, 사전 작업들(각 입력의 인덱스 2부터 끝까지)을 돌면서, 사전 작업들을 하기 위한 비용 중 가장 큰 값을 prev_max_time에 저장한다. 이 값은 초기에 0으로 초기화되기 때문에 사전작업이 없는 경우에는 0이 들어간다.

그리고 cost는 다음과 같은 식이 성립한다.

costs[x] = prev_max_time + current_time

즉, 작업 X를 마치기 위해선, (그것을 위한 사전작업들 중 비용이 가장 큰 것) + (작업 X의 비용)이 든다는 것이다.

 

이렇게 반복문을 마치고 비용들 중 가장 큰 값을 출력하면 된다.