[골드4] 2056번 : 작업

🛠 문제

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

👩🏻‍💻 해결 방법

위상정렬과 DP를 사용하여 해결 할 수 있는 문제다
graph에 연결된 작업들의 시간을 max를 사용해 최댓값을 갱신해주어야 한다
(위상정렬을 사용하지 않아도 해당 문제를 해결할 수 있다,,)

소스 코드

from collections import deque

n = int(input())
indegree = [0] * (n+1)
graph = [[] for _ in range(n+1)]
dp = [0] * (n+1)
times = [0]

for i in range(1, n+1):
  arr = list(map(int, input().split()))
  times.append(arr[0])
  # 1번이 아닐 경우
  if arr[1] != 0:
    for j in range(2, len(arr)):
      graph[arr[j]].append(i)
      indegree[i] += 1

q = deque()
for i in range(1, n+1):
  if indegree[i] == 0:
    q.append(i)
    dp[i] = times[i]

while q:
  now = q.popleft()
  for i in graph[now]:
    indegree[i] -= 1
    dp[i] = max(dp[now] + times[i], dp[i])
    if indegree[i] == 0:
      q.append(i)

print(max(dp))

💡 다른 사람의 풀이

import sys
input = sys.stdin.readline

n = int(input())
times = [0] * (n+1)
graph = {}

for i in range(1, n+1):
  lst = list(map(int, input().split()))
  times[i] = lst[0]

  if lst[1] == 0:
    continue
  for j in lst[2:]:
    if i in graph:
      graph[i].append(j)
    else:
      graph[i] = [j]

for i in range(1, n+1):
  if i in graph:
    time = 0
    for j in graph[i]:
      time = max(time, times[j])
    times[i] += time

print(max(times))