[백준] 퇴사2 파이썬 DP

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

15486번: 퇴사 2

 

내 첫 DP 문제... 어렵다 어려워... 처음에 DP라는 걸 모르고 그냥 풀었다가 시간초과나서 이게 뭐지 싶었음. 

 

 

<DP를 몰랐을 때 쌩구현 코드>

#퇴사2 DP - 내가 dp를 몰랐을 때. 

n=int(input())
day=0
total=0

t=[]
p=[]

for i in range(n):
    T,P=map(int,input().split())
    t.append(T)
    p.append(P)

max_pay=0
for i in range(n):
    day=i+1   #0+1=1, 4, 5
    total=0
    while True:
        if day+t[day-1]<n+1:
            total+=p[day-1] #p[0]=10, total=10
            day+=t[day-1] #t[0]=3, day=3,[3]=1
        elif day+t[day-1]==n+1:
                total+=p[day-1] #p[0]=10, total=10
                #day+=t[day-1] #t[0]=3, day=3,[3]=1
                break
        else:
            break

    if max_pay<total:
        max_pay=total


print(max_pay)

 

이렇게 푸니 시간초과가 나왔다. 

 

 

<DP를 알고 난 뒤 코드 - 구글링을 통해 해결>

 

#퇴사 dp 2번째 시도
import sys
input=sys.stdin.readline

N=int(input())
dp=[0 for i in range(N+1)]

#0,1,2,3,4,5,6
for i in range(N):
    t,p=map(int,input().split())

    dp[i+1]=max(dp[i+1],dp[i])
    
    if i+t<N+1:
        dp[i+t]=max(dp[i+t],dp[i]+p)


print(dp[-1])

 

처음에 sys.stdin.readline을 쓰지 않았다가 또 시간초과가 되었다... 파이썬으로 시간초과 피하기란 쉽지 않다. 위의 코드를 이해하는데도 한참 걸렸다.

 

 

<과정>

1. 우선, sys.stdin.readline() 함수를 사용하여 한 줄씩 입력을 받는다. 이 함수는 빠른 입력을 처리하기 위해 사용된다.
2. 첫 번째 입력으로는 일의 개수 N을 받는다.
3. 그 다음 N개의 줄에는 걸리는 일수, 금액을 입력. 
4. 이후에는 N일 동안의 최대 수익을 저장하기 위한 리스트인 dp를 초기화합니다. dp[i]는 i일까지의 최대 수익을 나타낸다.
5. 반복문을 통해 각 날짜에 대해 최대 수익을 갱신해 나갑니다. 각 날짜에 대해 두 가지 경우를 고려.
   • 해당 날짜를 포함하지 않을 경우(dp[i]) : 이전 날짜의 최대 수익과 동일. 이전 날짜 까지의 최대 이익이다. 다시 말해 현재 날짜에 일을 하지 않고 이전 날짜 까지의 최대 이익을 의미. 
   • 해당 날짜를 포함할 경우(dp[i+t]) : 해당 날짜에 일을 수행하고 수행 완료된 날짜(i+t)까지의 최대 수익과 해당 일을 마치고 얻을 수 있는 수익(p)을 더한다.  혀냊 날짜를 포함해 일을 수행할 경우의 최대 이익을 의미, 현재 날짜부터 t일 동안의 작업을 수행하고 그 일을 마치면 얻을 수 있는 이익을 현재 날짜부터 t일 동안의 최대 이익에 더한 값. 
6. 모든 날짜에 대해 최대 수익을 갱신한 후, 마지막 날의 최대 수익인 dp[-1]을 출력