[백준][14501] 퇴사

• 문제
  • 14501번: 퇴사
• 해결

import sys

resignation_day = sys.stdin.readline()

time_and_pay = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]

time_list = [x[0] for x in time_and_pay]
pay_list = [x[1] for x in time_and_pay]
cand = [0]

def go(time_list, pay_list, cur_ind, cumulative_pay):
    # 불가능
    if cur_ind >= len(time_list):
        return None

    # 정답
    if (cur_ind + time_list[cur_ind]) > len(time_list):
        if cand[0] < cumulative_pay:
            cand[0] = cumulative_pay
    if (cur_ind + time_list[cur_ind]) == len(time_list):
        if cand[0] < (cumulative_pay + pay_list[cur_ind]):
            cand[0] = cumulative_pay + pay_list[cur_ind]

    go(time_list, pay_list, cur_ind + time_list[cur_ind], cumulative_pay + pay_list[cur_ind])
    go(time_list, pay_list, cur_ind + 1, cumulative_pay)

    return cand[0]

print(go(time_list, pay_list, 0, 0))

• 포인트
  • Dynamic programming