[백준] 14501. 퇴사

문제

백준 14501.퇴사 https://www.acmicpc.net/problem/14501

 

코드 (바텀업 DP)

바텀업 방식에서는 뒤에서부터 접근하며 최적의 상담 스케줄을 결정한다.

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

for i in range(N)[::-1]:
    if i + table[i][0] > N:
        dp[i] = dp[i+1]
    else:
    	# i번째 날부터 얻을 수 있는 최대 이익
        dp[i] = max(dp[i + table[i][0]] + table[i][1], dp[i + 1])

print(dp[0])

 

풀이

for i in range(N)[::-1]:

N번째 날부터 거꾸로 탐색한다.

if i + table[i][0] > N:
    dp[i] = dp[i+1]

상담이 기간을 초과하면 다음 날의 값을 그대로 가져온다.

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

상담을 진행할 경우와 진행하지 않을 경우 중 최댓값을 선택한다.

 

시간 복잡도

O(N): 각 날짜를 한 번씩 확인하면서 최적의 상담 일정을 결정한다.

 

코드 (탑다운 DP)

탑다운 방식에서는 재귀를 활용하여 각 날짜에서 선택할 수 있는 최적의 상담을 찾는다.

N = int(input())
table = [list(map(int, input().split())) for _ in range(N)]
dp = [-1 for _ in range(N+1)]

def recur(day):
    if day == N:
        return 0
    if day > N:
        return -999999
    if dp[day] != -1:
        return dp[day]
    
    dp[day] = max(recur(day + table[day][0]) + table[day][1], recur(day + 1))
    return dp[day]

recur(0)
print(dp[0])

 

풀이

if day == N:
    return 0

상담이 끝난 경우 0을 반환한다.

if dp[day] != -1:
    return dp[day]

이미 계산된 값이 있다면 그대로 반환하여 중복 연산을 방지한다.

dp[day] = max(recur(day + table[day][0]) + table[day][1], recur(day + 1))

현재 상담을 진행하는 경우와 진행하지 않는 경우 중 최댓값을 갱신한다.

 

시간 복잡도

O(N): 메모이제이션을 적용하여 중복 연산을 줄였다.

 

코드 (백트래킹)

백트래킹 방식에서는 가능한 모든 상담 조합을 탐색하며 최대 이익을 찾는다.

def recur(day, money):
    global answer

    if day > n + 1:
        return 
    
    if day == n + 1:
        answer = max(money, answer)
        return 
    
    recur(day + table[day][0], money + table[day][1])
    recur(day + 1, money)

n = int(input())
table = [[] for _ in range(n+1)]

for i in range(n):
    a, b = map(int, input().split())
    table[i+1] = [a, b]

answer = 0 
recur(1, 0)
print(answer)

 

풀이

if day > n + 1:
    return

상담 일정을 초과한 경우 종료한다.

if day == n + 1:
    answer = max(money, answer)
    return

상담이 끝난 경우, 현재까지 얻은 이익을 최대값으로 갱신한다.

recur(day + table[day][0], money + table[day][1])

상담을 진행하는 경우 재귀 호출한다.

recur(day + 1, money)

상담을 진행하지 않고 다음 날로 이동한다.

 

시간 복잡도

O(2^N): 모든 경우의 수를 탐색하기 때문에 DP보다 비효율적이다.

 

비교 및 결론

방법시간	복잡도	장점	단점
바텀업 DP	O(N)	직관적이며 빠름	배열 크기 제한 있음
탑다운 DP	O(N)	재귀 기반으로 가독성이 높음	재귀 호출로 인한 오버헤드 가능
백트래킹	O(2^N)	모든 경우를 탐색하여 최적해 보장	비효율적, N이 커지면 사용 불가

가장 효율적인 방법은 바텀업 DP 또는 탑다운 DP이다.