100년 뒤 개발자 한승규입니다.

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

브루트포스 문제들을 모아서 풀다가 풀어보니 크게 어렵지 않게 풀 수 있었다.

간단하게 해당 일정을 추가하는 것과 안추가 하는 것들을 비교해보면 된다.

물론 이 방법도 경우의 수가 엄청 많이 나올 것이다.

def consult(today, cur):
    if today == N:
        return cur
    elif today > N:
        return 0
    else:
        return max(consult(today + 1, cur), consult(today + schedule_list[today][0], cur + schedule_list[today][1]))

사용한 함수이다.

만약 today가 딱 N 안으로 끝났다면 더 이상 추가할 수 없으니, 그냥 현재의 이익을 반환한다.

만약 today가 N을 벗어났다면, 해당 스케줄은 사용할 수 없는 스케줄이니 그냥 0을 반환해버린다.

위의 2가지 경우 모두 해당되지 않는다면, 해당 스케줄을 추가하는 것과 추가하지 않는 것을 다시 재귀함수에 넣어서 그 중 큰 값을 반환한다.

import sys

N = int(sys.stdin.readline())

schedule_list = []

for i in range(N):
    T, P = map(int, sys.stdin.readline().split())
    schedule_list.append([T, P])


def consult(today, cur):
    if today == N:
        return cur
    elif today > N:
        return 0
    else:
        return max(consult(today + 1, cur), consult(today + schedule_list[today][0], cur + schedule_list[today][1]))


print(consult(0, 0))