(BOJ)-14501, Python

문제 요약

출처: (BOJ)14501 - 퇴사

퇴사($N+1$)까지 $N$일이 남았고, 하루에 하나씩 상담이 주어진다. 각 상담은 기간($T$)와 보수($P$)로 구성된다. 남은 기간동안 완료할 수 있는 상담을 선택해 받을 수 있는 최대 보수를 구하는 문제이다.

• 상담 기간은 일 단위이며, 상담 일정은 서로 겹치지 않도록 선택해야 한다.

접근 과정

1. 완전탐색 접근(재귀)

상담을 선택하는 경우와 선택하지 않는 경우로 나누기 위해 재귀를 활용하여 접근하기로 했다.

코드 구현

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

def recursion(idx, day, pay):
    global max_price
    if idx > N:
        return
    if idx == N:
        max_price = max(max_price, pay)
        return
    #예약한 경우
    recursion(idx + counsel_list[idx][0], day+ counsel_list[idx][0], pay + counsel_list[idx][1])
    #예약하지 않은 경우
    recursion(idx+1, day, pay)

max_price = -1
recursion(0, 0, 0)
print(max_price)    

2. DP 접근(메모이제이션)

위에서는 재귀함수를 사용해 모든 경우의 수를 탐색하는 방식으로 접근했지만, 이 과정에서 동일한 경우를 여러 번 계산하는 중복 계산이 발생한다.. 이를 최적화할 수 있는 방법이 바로 동적 계획법(DP)이라고 생각한다.

예를 들어, 아래와 같이 상담 목록이 주어졌다고 하자:

일	1	2	3	4	5	6	7
$T$	4	1	3	1	2	2	1
$P$	10	20	30	40	35	150	10

뒤에서부터 1일씩 떼어 보면서 생각해 보자.

1. 7일차만 생각하면:
   • 7일차 상담을 진행하는 것이 이득이다.
   • dp[7] = max(상담할거냐, 안할거냐) == 10
2. 6~7일차를 생각하면:
   • 6일차 상담을 선택하는 것이 이득이다.
   • 이때, 7일차 상담을 선택하는 것은 얻는 보수가 더 작기 때문에 무시된다.
   • dp[6] = max(상담할거냐, 안할거냐) == 150
3. 5~7일차를 생각하면:
   • 5일차 상담을 선택하는 것은 이득이 아니다.
   • 대신, 6일차 상담을 선택하는 것이 더 큰 보수를 가져온다.
   • dp[5] = max(상담할거냐, 안할거냐) == 150

이렇게 백트래킹을 하며 각 일차에서의 가장 높은 보수를 기억해 둔다면, 이후 해당 값을 재사용함으로써 불필요한 계산을 줄일 수 있다:)

코드 구현

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

def recursion(idx):
    if idx > N:
        return -1e9 
    if idx == N:
        return 0 
    if dp[idx] != -1:
        return dp[idx]
    #상담을 받거나, 안받거나
    dp[idx] = max(recursion(idx + counsel_list[idx][0]) + counsel_list[idx][1], recursion(idx+1))
    
    return dp[idx]
    
    
dp = [-1 for _ in range(N)]

recursion(0)
print(max(dp))   

회고

재귀로도 충분히 풀리는 문제였다. 하지만 DP랑 재귀 완전탐색의 연관성을 알게 되어 시도해보았다. 직접 DP를 활용하며 느낀 점은, 재귀 완전탐색에서 크게 달라진 것은 없고, 중복 계산을 줄이기 위해 누적합 개념을 추가한 정도라는 것이다.