[BOJ-14501] 퇴사

 

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

14501번: 퇴사

---

[풀이]

전형적인 DP문제이다.

이문제를 통해서 DP가 미숙함을 알게됐다.

좀더 공부해야겠다.

 

이 문제에서 주의해야할 점이

i번째날에 일을 하면, i+1번째날에 돈을 받는다.

반면 i번째날에 일을 안하면, i+1번째날은 돈을 받지않는다.

 

 

그리고 예제4번이 왜 90이 나오는지를 이해해야한다.

 

설명이 잘되어있는 블로그 2가지가 있다.

본인도 여기에 참고했다.

 

백준 14501 퇴사

 

 

백준 14501번 퇴사 [DP] :: 마이구미

---

[코드]

import sys
from copy import deepcopy
input=sys.stdin.readline

MAX_DAY=17
T=[0]*(MAX_DAY)
P= [0]*(MAX_DAY)
DP=[0]*MAX_DAY

#입력
N=int(input()) 
for i in range(1,N+1):
    T[i], P[i]= map(int, input().strip().split())

MAX=0
#   N번째날에 일한다면, N+1번째 날에 돈을 받는다.
for i in range(1,N+1):
    #i번째날에 일을 한경우-> (i+1)번째날에 돈을 받는다.
    if i+T[i]<=N+1:
        DP[i+T[i]]=max(DP[i+T[i]], DP[i]+P[i])
        MAX= max(MAX, DP[i+T[i]])
        
    #i번째날에 일을 안한 경우-> (i+1)번째날에 돈을 받지 않는다.
    DP[i+1]=max(DP[i+1], DP[i])
    MAX=max(MAX, DP[i+1])

print(MAX)

 

[Java]