백준 14501 퇴사 (파이썬)

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

14501번: 퇴사

1. 상담에 걸리는 기간과 금액을 리스트 a에 저장한다

2. dfs 조합으로 상담할 날짜를 고른다

   퇴사일에서 현재 날짜를 뺐을 때의 값이 상담 기간보다 크거나 같은 날짜만 선택해야한다

3. 상담 일정을 정했으면 모든 금액을 더한 후 ans에 최대값을 저장한다

import sys

input = sys.stdin.readline

def dfs(idx):
    global ans
    for i in range(idx, n):
        if select[i]:
            continue
        if n - i >= a[i][0]:
            select[i] = 1
            dfs(i + a[i][0])
            select[i] = 0

    res = 0
    for i in range(n):
        if select[i]:
            res += a[i][1]
    ans = max(ans, res)

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

select = [0 for _ in range(n)]
ans = 0
dfs(0)
print(ans)