악곱 == 악성곱슬

다이나믹 프로그래밍, 브루트 포스

---

본 문제는 입력 N의 개수가 최대 15이다. 따라서 2^15 즉, 완전탐색을 통해 구현해도 시간에 걸리지 않는 문제이다. 만약 N이 커진다면 다이나믹 프로그래밍을 사용하여 구현해야 한다.

DP를 사용한 코드는 아래와 같다.

import sys

def solution(table, n):
    result = [0] * (n + 2)
    if table[n][0] == 1:
        result[n] = table[n][1]
    for i in range(n-1, 0, -1):
        t, p = table[i]
        # 인덱스 범위 벗어남
        if i + t > n + 1:
            result[i] = result[i + 1]
            continue
        result[i] = max(result[i + 1], result[i + t] + p)
    return max(result)

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    Table = [[0]*2 for _ in range(N + 1)]
    for idx in range(1, N+1):
        T, P = map(int, sys.stdin.readline().rstrip().split())
        Table[idx][0] = T
        Table[idx][1] = P
    print(solution(Table, N))