[백준/브루트포스] 14501 퇴사(Python, 파이썬)

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

14501번: 퇴사

 

 

어떤 날은 상담을 하는 것이 좋고, 어떤 날은 오히려 상담을 안하는 것이 좋다. 

안하는 것이 좋은 날은 이후에 상담을 하게 되는 것이 수익이 더 많은 경우이다.

이것은 상황에 따라 그때그때 다르니 모두 해보는 것이 좋다.

 

sum: day-1일까지의 수익

 

 1. 상담을 한다: go(day+T[day], sum+P[day])

- 현재 날짜에서 상담을 할 경우 걸리는 날짜를 더해준다.

- 현재까지 얻은 수익에서 상담을 할 경우 얻게 되는 수익을 더해준다.

 

2. 상담을 안한다: go(day+1, sum)

- 상담을 안하고 다음날로 넘어가므로 현재 날짜에서 하루를 더해준다.

- 상담을 안하므로 얻는 수익은 변함이 없다.

 

3. 정답을 찾은 경우: day == n+1

- 현재 날짜가 퇴사날인 경우

 

4. 불가능한 경우: day > n+1

- 현재 날짜가 퇴사날을 넘어가는 경우는 불가능하다.

 

 

import sys
input = sys.stdin.readline

def go(day, sum):
    global answer

    # 종료조건: 퇴사날에 딱 맞췄을 때
    if day == n+1:
        answer = max(sum, answer)
        return

    # 불가능한 경우: 상담을 했을 때, 퇴사날을 넘어가는 경우
    if day > n+1:
        return
    
    # 상담을 한다
    go(day+t[day], sum+p[day])

    # 상담을 안한다
    go(day+1, sum)

# n+1일째 되는 날 퇴사
n = int(input())
t = [0] * (n+1)
p = [0  ] * (n+1)
answer=0

for i in range(1, n+1):
    t[i], p[i] = map(int, input().split())

go(1, 0)
print(answer)