[백준] 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

dfs 또는 dp를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

각각의 상담은 소요시간과, 받을수 있는 금액으로 구성되어 있습니다. 매일 상담이 있을 때, 상담을 통해 최대 수익을 얻는 경우의 최대 수익의 값이 얼마인지를 구해야 하는 문제입니다.

 

dfs와 dp를 사용한 풀이 두가지 모두 설명해 보겠습니다.

 

<Solution>

방법 1. DFS를 이용한 풀이

문제의 조건처럼 상담이 아래 그림과 같이 주어진다고 생각해 봅시다. 

우리는 매 상담에 대해, 이 상담을 할지 말지를 결정합니다. 

 

간단한 예시로 1일차를 생각해봅시다.

• 1일차에 상담을 진행하게 되면, 다음은 4일차의 상담을 진행할지 하지 않을지 두가지 경우에 대해 dfs과정을 반복하면 됩니다. 
• 1일차에 상담을 진행하지 않게 되면, 다음은 2일차의 상담을 진행할지 하지 않을지 두가지 경우에 대해 같은 과정을 반복하면 됩니다.

이러한 과정을 쭉 진행하면 문제를 해결할 수 있습니다.

 

실제 구현은 아래와 같습니다.

import sys

N = int(sys.stdin.readline().rstrip())

advice = [[]]
for i in range(N):
    advice.append(list(map(int, sys.stdin.readline().rstrip().split())))

max_p = -1
s = 0
def dfs(current_date):
    global s
    global max_p
    if current_date == N+1:
        max_p = max(max_p, s)
        return
    
    # accept if available
    duration = advice[current_date][0]
    if current_date + duration <= N+1:
        s += advice[current_date][1]
        dfs(current_date + duration)
        s -= advice[current_date][1]

    # reject
    dfs(current_date + 1)

dfs(1)
print(max_p)

방법 2. DP를 이용한 풀이

위의 DFS를 이용한 풀이 방법을 생각해보면, 중복된 연산이 포함되는 것을 알 수 있습니다. 만약 현재 날짜의 상담을 받지 않고 계속 reject 시키는 상황만 반복된다고 생각해봅시다. 

 

첫째날 상담을 수락하면, 위의 코드 상황에서 current_date 는 1에서 4로 되게 됩니다. 이 상황은 1일차 부터 3일차 까지 모든 상담을 reject 시킨 상황과 동일합니다. (이 상황에서도 current_date = 4) 

 

따라서 우리는 이러한 current_date가 같고, 현재 진행중인 상담도 없는 경우가 중복 되어 연산되는 것을 알 수 있습니다. 이러한 것을 DP를 이용하면 없앨수 있습니다. 

 

DP array를 DP[i] = i일차부터 끝까지 진행되었을 때의 얻을수 있는 최대 비용으로 정의 합니다. 

 

그러면 DP array를 가장 뒤에서 부터 앞으로 채우면서, 현재 i번째 날짜에

상담이 가능한 경우,

dp[i] = max(advice[i][1] + dp[i + advice[i][0]], dp[i+1])

상담이 불가능한 경우, 

dp[i] = dp[i+1]

이렇게 dp를 뒤에서 부터 채워나갈 수 있습니다. 

 

실제 구현은 아래와 같습니다.

import sys

N = int(sys.stdin.readline().rstrip())

advice = [[]]
for i in range(N):
    advice.append(list(map(int, sys.stdin.readline().rstrip().split())))

dp = [0] * (N+2)

for i in range(N, 0, -1):
    # if advice available
    if advice[i][0] + i <= N+1:
        dp[i] = max(advice[i][1] + dp[i + advice[i][0]], dp[i+1])
    # not available
    else:
        dp[i] = dp[i+1]

print(dp[1])

실제로 시간이 미세하지만 개선 된 것을 확인할 수 있습니다.