[백준 14501] 퇴사 with Python

문제 링크

www.acmicpc.net/problem/14501

14501번: 퇴사

풀이

import sys

n = int(sys.stdin.readline())
tp = []
for i in range(n):
    tp.append(tuple(map(int, sys.stdin.readline().split())))
maximum_profit = 0

def search_maximum_profit(start, acc=0):
    global maximum_profit
    profit = acc
    if start < n and start+tp[start][0]-1 < n:
        profit += tp[start][1]
        for i in range(start+tp[start][0], n+1):
            search_maximum_profit(i, acc=profit)
    else:
        if maximum_profit < profit:
            maximum_profit = profit

for i in range(n):
    search_maximum_profit(i)

print(maximum_profit)

먼저 각각의 날짜의 T와 P를 튜플로 묶어 tp에 저장한다. 그리고 각 날짜에 대해 search_maximum_profit을 시행한다.

 

- search_maximum_profit은 start로 직전에 상담하기 시작한 날짜를, acc로 누적 금액을 받는다.

 

- 먼저 직전의 상담시작일이 퇴사 전인지(start < n), 그리고 그 상담을 마친 날짜 역시 퇴사 전인지(start+tp[start][0]-1) 확인하여 참이면 profit에 상담시작일의 금액을 더하고(profit의 초기값은 인자로 받은 acc와 같다), 반복문으로 넘어가서 현재 날짜(start+tp[start][0])와 지금까지의 누적금액인 profit을 인자로 search_maximum_profit을 재귀호출한다. 

 

- 거짓이면 더 이상 상담을 진행할 수 없는 상태이므로 누적 금액이 maximum_profit보다 높으면 maximum_profit을 갱신한다.

 

이 과정을 거치면 낭비되는 날이 없이 상담을 하는 모든 경우를 확인하여 더 높은 금액이 나오는 경우가 나올 때마다 maximum_profit이 갱신되어 결국 최대 수익이 된다.

 

 

위 문제를 푸는 과정에서 maximum_profit을 전역 변수로 두고 search_maximum_profit에서 global을 이용하여 maximum_profit에 접근하였다. global을 사용하는 것을 권장하지 않는다는 말을 들은 적이 있어서, 어떻게 하면 global을 쓰지 않고 풀 수 있을지 더 생각해 봐야겠다.