파이썬 알고리즘 205번 | [백준 2056번] 작업 DP

205. 작업

1) 어떤 전략(알고리즘)으로 해결?

DP

2) 코딩 설명

<내 풀이>

from collections import deque
import sys

# 첫째 줄에 N
# 두 번째 줄부터 N+1번째 줄까지 N개의 줄
# 작업에 걸리는 시간, 작업에 대해 선행 관계에 있는 작업들의 개수,
# 선행 관계에 있는 작업들의 번호
# 서로 선행 관계가 없는 작업들은 동시에 수행

n = int(sys.stdin.readline().rstrip())
task = deque();time = 0

for i in range(n) :
    lis = list(map(int, sys.stdin.readline().rstrip().split()))
    t= lis[0]; precnt = lis[1]; time+=lis[0]

    if precnt>0: 
        people = lis[2:]; 
        task.append((t, precnt, people))

    else : 
        task.append((t, precnt, -1))

dp = [0 for _ in range(n)] # 

for i in range(n) :
    now = task.popleft()
    #print(dp, now[0])
    if now[2]== -1:
        dp[i] = dp[i] + now[0]
    else : 
        maxx = -99999
        for p in now[2] :
            # 나보다 선행돼야 하는 애들 중 가장 끝나는 시간 늦은 애 찾아
            # 걔 다음에 수행되면 된다. 
            if maxx<dp[p-1] : maxx = dp[p-1]
        dp[i] =  + now[0]+maxx

print(max(dp))

<내 틀렸던 풀이, 문제점>

9프로에서 틀림

from collections import deque
import sys
n = int(sys.stdin.readline().rstrip())
# 첫째 줄에 N
# 두 번째 줄부터 N+1번째 줄까지 N개의 줄
# 작업에 걸리는 시간, 작업에 대해 선행 관계에 있는 작업들의 개수,
# 선행 관계에 있는 작업들의 번호
# 서로 선행 관계가 없는 작업들은 동시에 수행
task = deque();time = 0

for i in range(n) :
    lis = list(map(int, sys.stdin.readline().rstrip().split()))
    t= lis[0]; precnt = lis[1]; time+=lis[0]

    if precnt>0: 
        people = lis[2:]; 
        task.append((t, precnt, people))

    else : 
        task.append((t, precnt, -1))

dp = [0 for _ in range(time+1)]
last_task_time = task[-1][0]
for i in range(n) :
    now = task.popleft()
    #print(dp, now[0])
    if now[2]== -1:
        dp[i] = dp[i] + now[0]
    else : 
        maxx = -99999
        for p in now[2] :
            if maxx<dp[p-1] : maxx = dp[p-1]
        dp[i] =  + now[0]+maxx
    lastdp  = dp[i]

print(lastdp)

<반성 점>

<배운 점>