baekjoon. 15486 퇴사 2 [Gold V][python]

 

https://ddoance.tistory.com/108

⚡️ baekjoon. 14501 퇴사 [Silver III][python]

 

이 문제의 어려운 버전으로, Gold V 레벨이 있다. 

이 풀이로 작동하지 않았고, 결국 dp로 다시 풀어야 했다.

 

시간초과가 발생할 경우, input을 받는 형식을 바꿔줘야 한다. 

https://animoto1.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EC%8B%9C%EA%B0%84-%EC%B4%88%EA%B3%BC-%ED%95%B4%EA%B2%B0%EB%B0%A9%EB%B2%95

파이썬(Python) 시간 초과 해결방법

 

 

 

최종 풀이는 다음과 같다. 

import sys
input = sys.stdin.readline 

N = int(input())


meetingList = list()
for _ in range(N):
    meetingList.append(list(map(int, input().split())))


dp = [0] * (N + 1)

for i in range(1, N + 1):
    time = meetingList[i - 1][0]
    price = meetingList[i - 1][1]

    # 회의 참석할 경우 
    if (i + time - 1) <= len(meetingList):
        dp[i + time - 1] = max(dp[i + time - 1], dp[i - 1] + price)

    ### 회의 참석 안할 경우, 그 전날 값을 가져옴 
    if dp[i - 1] > dp[i]:
        dp[i] = dp[i - 1]
    ###
    # print(i, ' >> ', dp)

print(max(dp))