퇴사

 

 

유형파악 및 구현

이 문제는 아이디어는 떠올리기 쉬웠으나 구현이 어려웠던것 같다.

아이디어

- 우선, 뒤에서부터 하나하나 확인을 한다.

- 만약 걸리는 시간때문에 퇴사전 이 일을 마무리 못하는 경우라면 패스한다.

- 가능하다면 추가를 한다.

- 다음의 경우로 마지막날 전날 인터뷰에 대해서 점검을 하는데

예를들어, 7일까지 일을할 것이고 7일은 1일소요, 500원, 6일은 2일소요 100원이라고 가정하자

6일날 일하게 되면 6,7일은 일을 못하고 다음일은 8일부터 가능하다.

따라서 7일날 일하는 경우 vs 6일날 버는 돈 + 8일 이후에 버는돈 을 비교해 큰값으로 값을 기록한다.

이 후, 그 전날 , 그 전날 이런식으로 나아간다.

 

전형적인 DP문제이다. 하지만 헷갈렸던 거는, 기록을 하는 dp리스트는 크기가 (n+1)이고 graph는 n이고 다음에 일하는 경우가 n을 넘는 등 암튼 헷갈리는게 많아서 구현이 좀 까다로웠다.

 

 

# 데이터의 크기
n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

# 최대 금액을 기록하기 위한 dp리스트
# ex) dp[3] : 4~n일 까지 일했을 때, 최대 버는 돈
dp = [0]*(n+1)
max_value = 0

# 리스트를 뒤에서부터 확인
for i in range(n-1, -1, -1):
    money = graph[i][1]
    again_work = graph[i][0]+i

    if again_work <= n:
        dp[i] = max(dp[again_work]+money, max_value)
        max_value = dp[i]
    else:
        dp[i] = max_value
print(dp[0])