문제
N+1일째 되는 날 퇴사를 하기 위해, 남은 N일 동안 최대한 많은 일을 하려고 합니다. 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아 놓았습니다. 상담을 적절히 했을때 백준이가 얻을 수 있는 최대 수익을 구하는 문제입니다.
풀이
함수를 정의 합니다. dfs(start_day) : 현재 날짜부터 시작해서 얻을 수 있는 수익
해당 함수는 다음과 같이 쪼개집니다. 현재 날짜를 선택하고 현재 날짜가 소요하는 기간 이후의 날짜에 대해 재귀처리합니다.
다시 말하면
dfs(3)은
10 + 최대값(dfs(4) / dfs(5) / dfs(6) / dfs(7) / dfs(8))입니다.
범위(현재날짜+소요날짜 ~ N+1)를 지정하고 재귀함수를 호출하면 됩니다.
N+1까지 호출을 해줘야하는데 이는 7일째 되는날(마지막날) 소요기간이 1이라면 7일을 모두 소모해서 상담을 끝마칠수있습니다. 여기서 범위를 N으로 잡게 된다면 8~7 이므로, 해당 상담이 유효하지 않아서 해당 상담은 이루어지지 않게 됩니다.따라서 이 경우까지 생각하여 N+1을 포함한 범위를 가져야합니다. 물론 N+1일째에는 퇴사를 했으므로 도달시에 0을 반환합니다.
또 생각해 볼것은 dfs(1)에서의 dfs(5)와 dfs(3)에서의 dfs(5)의 값이 상이한지에 대해 생각해볼 필요가 있습니다. dfs(1)이던, dfs(5)이던 날짜에 상관없이 dfs(5)의 값은 같습니다. 따라서 최적부분구조를 만족하며 같은 부분문제가 반복되므로 결과값을 저장해서 재활용할 필요가 있습니다. 이 기법을 활용해서 최적화해주었습니다.
코드
'''
Created by jun on 21/05/28
'''
# 현재 시점을 기점으로 만들수있는 최대 이익을 반환한다.
def dfs(start_day):
# 퇴사했으므로 일을 시작할 수 없다.
if start_day == N + 1:
return 0
global memo
# 현재 시점이 저장되어 있는가?
if memo[start_day] != -1:
return memo[start_day]
# 현재 시점의 누적금액. 아직 일을 진행하지 않은 상태이다.
res = 0
# 현재시점을 진행하는데 드는 비용 = (시간비용, 돈비용)
time_cost, money_cost = bill[start_day]
# 기간내에 일을 끝내고 난 후의 범위
for day in range(time_cost + start_day, N + 2):
res = max(res, money_cost + dfs(day))
memo[start_day] = res
return memo[start_day]
N = int(input())
# (시간 , 비용)
bill = [(1, 0)] + [tuple(map(int, input().split())) for _ in range(N)]
memo = [-1] * (N + 1)
print(dfs(0))새로 알게된 사실
재귀를 호출함에 있어서 적절한 범위를 생각해야한다.
