[Python][백준/BOJ] 14501번 : 퇴사

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

14501번: 퇴사

 

내 코드

import sys
input = sys.stdin.readline

n = int(input())
t=[]
p=[]
dp = [0 for _ in range(n+1)] #금액 더할거임
for i in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
    
for i in range(n-1, -1, -1):
    if t[i]+i > n: #퇴사후까지 상담하게 생겼으면 패스
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], dp[t[i]+i] + p[i])

print(dp[0])

 

리뷰

 

DP

dp[i]에서 t일 후로 넘어가는 것이 어려워서 시간이 많이 걸렸던 문제이다.

dp의 특성은 0이나 1로 초기화를 해놓고 dp에 수를 더하면서 최대값을 구하거나 최소값을 구하는 것 같다.

for i in range(n-1, -1, -1):
    if t[i]+i > n: #퇴사후까지 상담하게 생겼으면 패스
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], dp[t[i]+i] + p[i])

이 문제를 풀 때는 퇴사 후까지 기간이 넘어선다면, 오늘자 상담 말고 다음날의 상담으로 계산한다.

그리고 만약 퇴사 전에 상담을 마칠 수 있다면 dp에 위와 같이 저장한다.

MAX(day + 1에 근무, day + t에 근무)

 

FOR문 조건

이 문제에서는 배열 t(상담 가능한 일자)의 조건이 중요하다. t가 n을 넘어서면 안된다는 조건이다.

그래서 처음에는 for문(n)으로 풀면서 if문으로 배제했다가, for문을 거꾸로 하면 코드가 훨씬 간결해짐을 알게 되었다.

for(n-1, -1, -1)

이 for문은 저번 문제에서도 이렇게 풀어야 했고, 난이도가 높아질수록 자주 등장하는 것 같으니 잘 활용하자.