[백준] 14501 퇴사 - 재귀 (Python)

먼저 2 차원 배열로 상담 시간과 수익을 저장한다. 

 

현재 작업 중인 i 번째 리스트 인덱스 값에 i 번째 리스트의 값을 더했을 때  보다 작다면, 수익에 해당 값을 재귀 호출한 값과 수익을 더한다. 

현재 작업을 수행하지 않고 그냥 다음 작업으로 넘어가는 경우 두 경우 중 더 큰 값을 선택한다.

 

각 작업은 소요되는 시간이 정해져 있고 주어진 제한된 시간 안에서 최대한 많은 이익을 얻기 위해 어떤 작업을 선택해야 할지 재귀 호출을 통해 고민해 보았다.

 

1. 주어진 작업을 할지 말지 결정

2. 작업이 끝나는 시간을 넘지 않는 범위 내에서 최대 이익을 얻도록 재귀적으로 계산

 

재귀 -> 각 작업을 선택하거나 선택하지 않는 모든 경우를 탐색

n = int(input())

list = [list(map(int, input().split())) for _ in range(n)]

def recur(i) :
    if i >= n :
        return 0
    money = 0
    if i + list[i][0] <= n :
        money = recur(i + list[i][0]) + list[i][1]
    money = max(money, recur(i+1))
    return money
print(recur(0)) # 첫 번째 작업부터 시작

 

다른 사람의 풀이를 찾아보니 DP 를 사용한 풀이법이 많았다. 현재 코드에서는 재귀를 사용하지만 이전에 계산된 결과를 저장하지 않고 있어서 중복 계산이 발생할 수 있어 비효율적이라고 한다. 이미 계산된 값을 저장하고 재사용하는 방식으로 성능을 개선할 수 있다.

n = int(input())
TP = [list(map(int, input().split())) for _ in range(n)]
dp = [0 for _ in range(n+1)]

for i in range(n-1,-1,-1):
    if i+TP[i][0] > n:
        dp[i] = dp[i+1]
    else:
        dp[i] = max (dp[i+1],dp[i+TP[i][0]]+TP[i][1])
print(dp[0])