Hanbit the Developer
[Python] 백준 2056번: 작업 본문
https://www.acmicpc.net/problem/2056
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의 비용)이 든다는 것이다.
이렇게 반복문을 마치고 비용들 중 가장 큰 값을 출력하면 된다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 2533번: 사회망 서비스(SNS) (0) | 2021.08.26 |
---|---|
[Python] 백준 2568번: 전깃줄 - 2 (0) | 2021.08.25 |
[Python] 백준 1915번: 가장 큰 정사각형 (0) | 2021.08.24 |
[Python] 백준 14722번: 우유 도시 (0) | 2021.08.23 |
[Python] 백준 13302번: 리조트 (0) | 2021.08.22 |