퇴사2

문제

풀이

DP문제이고 입력값은 백만이 넘는 수가 주어지기 때문에 일차원 배열에서 단일 포문으로 문제를 풀어야 했다.

예제 입력 1 기준으로 설명하자면

Day1일 때 시간은 3만큼 걸리므로 4에 10을 추가한다.
하지만 이렇게 할 경우 1만큼 걸릴 때에는 당일치기이기 때문에 -1을 해주어서 3에 10을 추가한다.

Day2일 때 시간은 5가 소요되므로 2 + 5 - 1 = 6에 20을 추가한다.

Day3일 때 시간은 1이 소요되므로 3 + 1 - 1 = 3에 10을 추가한다.
하지만 기존 10과 현재 Day3의 값 10을 비교한 10을 넣어준다.

Day4일 때 시간은 1이 소요되므로 4 + 1 - 1 = 4에 20을 추가한다.
하지만 이전에 dp값 10이 존재하므로 10+20=30을 넣어준다.

Day5일 때 시간은 2이 소요되므로 5 + 2 - 1 = 6에 15을 추가한다.
하지만 이전에 dp값 30이 존재하므로 30+15=45을 넣어준다.
또한 dp[6]에 20에 존재하므로 큰 값을 넣어준다.

Day6일 때 범위가 벗어나므로 그대로 적어준다.

Day7일 때 범위가 벗어나므로 그대로 적어준다.
그리고 이전 dp값과 비교하여 큰 값을 가져온다.
max(45,0) = 45

def solution():
    n = int(sys.stdin.readline())
    graph = [[]] + [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    dp = [0 for _ in range(n + 1)]

    for i in range(1, n + 1):
        dp[i] = max(dp[i], dp[i-1])
        if i + graph[i][0] - 1 <= n:
            dp[i + graph[i][0] - 1] = max(dp[i + graph[i][0] - 1], dp[i - 1] + graph[i][1])

        print(dp)

    print(dp[-1])
solution()

즉 현재 날짜 + 걸리는 시간을 기준으로 DP테이블을 만들었고
걸리는 시간을 더했기 때문에 현재 인덱스는 비어있을 수 있다. 그렇기 때문에 이전값과 비교하여 큰 값을 넣어주었다.