백준 14501 퇴사 (파이썬)

풀이 및 해설

import sys
sys.setrecursionlimit(10**6)

# index = 현재 일정, profit = 현재까지의 수익
def solve(index, profit):
    global rst
    # index가 초과하면 rst를 갱신
    if index >= N:
        rst = max(rst, profit)
        return
    # 상담 소요일
    now_num = meeting[index][0]
    # 상담 수익
    now_profit = meeting[index][1]
    # 현재 상담을 안하고 다음날로 넘어가기
    solve(index+1, profit)

    # index에러 방지 == 상담 할 수 있는 경우
    if now_num + index <= N:
        # 상담 진행
        solve(index+now_num, profit+now_profit)

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

meeting = []
for _ in range(N):
    val = list(map(int, sys.stdin.readline().strip().split()))
    meeting.append(val)

rst = -1
for i in range(N):
    solve(i, 0)

print(rst)

 

---

후기

• 이거랑 비슷한 유형의 문제가 되게 많았던걸로 기억한다..
• 일단, 첫 번째 날 부터 인덱스와 수익을 매개변수로 넘겨줘서 재귀는 index가 증가하는 형식이다.
• 현재의 상담을 포함하냐 포함하지 않느냐로 나눠 재귀로 넘겨준다.