백준 14501 퇴사 파이썬 문제풀이 (python 최적화, 재귀, 백트래킹 경우의 수)

문제 보러가기

 

백준 퇴사 파이썬 문제풀이 

N일까지 회사를 다니고 N+1일에 퇴사를 하는데,

그때까지 T일이 걸리는 상담을 하고 P가격을 받는다.

 

상담 기간동안은 다른 일을 맡지 못하기에,

가장 많은 가격을 받는 다면 얼마를 받을 수 있는지 구하는 문제이다.

 

만약 상담을 받으면 일자는 상담에 걸리는 시간만큼 넘어가야하고,

N+1일자를 넘어갈때까지 일은 못한다.

 

n = int(input())
work = []
answer = 0
def recur(day, prc):
    global answer
    if day > n:
        return
    if day == n:
        answer = max(answer, prc)
        return
    recur(day + work[day][0], prc+work[day][1])
    recur(day + 1, prc)

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

recur(0, 0)
print(answer)

그 두 조건을 고려해서

재귀함수 안에 if문을 만들고,

 

상담을 받으면 그만큼 날짜를 넘어가고,

안받으면 다음날로 진행해서 재귀한다.

 

주의할 점은 day가 n보다 크면(여기서는 0부터 시작하므로 N+1 - 1)

퇴사 날을 넘겨서 그 일은 끝내지 못하는 일이므로 중단한다.

맞았다~