[백준] 14501번: 퇴사 / 파이썬

문제 링크

---

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

풀이 코드

---

n = int(input())
T, P = [0 for i in range(n+1)], [0 for i in range(n+1)]
for i in range(n):
    a,b = map(int, input().split())
    T[i] = a
    P[i] = b
 
dp = [0 for i in range(n+1)]

for i in range(len(T)-2, -1, -1):
    if T[i]+i <= n:       # 날짜 초과하지 않았다면
        dp[i] = max(P[i] + dp[T[i] + i], dp[i+1]) #값 중 비교해서 높은 값 추가  
    else:                 # 날짜 초과
        dp[i] = dp[i+1]     #스킵
print(dp[0])

코드 해석

---

DP로 풀었다.

역순으로 진행하며

dp에는 i번째날까지 일했을 때 최댓값을 보관한다.

뒤에서부터 날짜를 초과하지 않는지 T값과 비교하여 확인하고

만약 날짜가 초과하지 않았다면

지금까지 일했을때의 최댓값과 들어온 값 중 비교하여 더 높은 수를 저장한다.

초과한다면 카운팅을 하나 뒤로 넘긴다.

 

DP는 너무 어렵다 ㅠㅠ

체감 난이도: ★★★★★