[DP] 백준 14501 퇴사

문제링크 www.acmicpc.net/problem/14501

 

처음에 DFS로 시도했는데 너무 어려워서 DP로 노선 변경하니까 금방 풀렸다,,,ㅎ

현재 일에 도달할 수 있는 날들 중 최대값을 찾아 현재 price+최대 price를 더해가면서 누적하면 풀리는 문제

 

 

[답코드]

import sys
input=sys.stdin.readline

n=int(input())
t=[]
p=[]
for _ in range(n):
    a, b = map(int, input().split())
    t.append(a)
    p.append(b)
# print(t, p)

# p에는 선택될 수 있는 값 중 가장 큰 값을 누적시킨다
for i in range(n):
    max_value=0
    for j in range(i):
        if j+t[j]<=i:
            # 일 수가 현재 일수를 넘지 않는 값 중 최대값 저장
            max_value=max(max_value, p[j])
    # p값 갱신
    p[i]=p[i]+max_value

result=0
for i in range(n-1, -1, -1):
    if i+t[i]<=n:
        result=max(result, p[i])
print(result)

 

 

[풀이법]

앞으로 p에는 현재값 + 전 일들 중 가장 큰 p의 값을 넣어준다

계속 누적시켜주면 답이 나온다

 

먼저 예제 1을 예시로 들어보면,

 

 

i가 3이면 max_value 후보에 들어갈 수 있는 값은

10 하나가 된다

왜? 현재 전에 상담을 끝낼 수 있는 날이 주황색 날 밖에 없어서

(초록색 - 현재값, 주황색 - 현재값에 더해질 수 있는 값)

 

그러면 현재 p값을 위에서 구한 max 날 + 현재 p값으로 갱신시켜 준다

 

 

 

그 다음 i가 4일 때 max_value의 후보는 10, 10, 30이 된다

후보들 중 30이 가장 크므로 p[i]의 값을 p[i]+30으로 갱신시켜 준다

 

 

 

이렇게 계속하면 최종적으로 위와 같은 p 리스트가 완성되고

그 중 t[i]+i의 값이 n을 넘지 않는 p 값 중 최대값을 선택해 출력하면 된다