[BOJ] #15486 퇴사2 (Python, Dynamic Programming, 시간 초과 해결)

🌱 문제

15486번: 퇴사 2

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

퇴사일과 각 일마다 상담에 소요되는 일수와 받을 수 있는 금액이 주어질 때, 얻을 수 있는 최대 이익을 출력하는 문제입니다.

백준 14501 퇴사 문제와 같은 문제인데, 시간복잡도를 줄여서 제출해야 맞출 수 있습니다.

세상 무서운 시간 초과,,

 

🌱 풀이 1 - 시간 초과

dp = [0 for _ in range(n + 1)]

for i in range(n):
    for j in range(i + meetings[i][0], n + 1):  # i일 상담 진행했을 때 상담 가능한 날부터 돌기
        dp[j] = max(dp[j], dp[i] + meetings[i][1])

print(dp[-1])

• dp[i]에는 i일까지 일했을 때의 최대 수익이 담깁니다.
• 이 풀이에서는 dp 배열을 완벽하게 채웁니다. 즉, 1일부터 n일까지 얻을 수 있는 최대 수익을 모두 구합니다.
• 2중 for문을 사용하여 i일에 시작한 상담이 끝나는 날부터 퇴사일까지 끝까지 순회합니다.
• 따라서 가장 마지막날을 바로 출력하면 퇴사일(n일)의 최대 수익을 출력할 수 있습니다.
• 하지만 이렇게 2중 for문을 돌게 되면 15486번에서는 시간 초가가 납니다.

 

🌱 풀이 2

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

# DP 풀이
profit = 0
for i in range(1, n + 1):
    end_date = i + meetings[i][0] - 1  # i일에 시작한 상담이 끝나는 날
    profit = max(profit, dp[i - 1])  # i일까지의 최대 수익
    if end_date <= n:  # 상담이 끝나는 날이 퇴사일을 넘지 않으면
        # 점화식 (현재 저장된 최대 수익과 i-1일까지의 최대 수익 + i일 상담 수익을 비교)
        dp[end_date] = max(dp[end_date], profit+meetings[i][1])

print(max(dp))

• 풀이1과는 다르게 i일에 시작한 상담이 끝나는 날의 dp만 업데이트를 합니다. (풀이1에서는 상담이 끝나는 날부터 퇴사일까지 끝까지 순회하도록 for문을 한 번 더 사용함)
• 대신, i-1까지의 최대 수익을 담고 있는 profit 변수를 사용하여 i-1일까지의 최대 수익에 i일 상담 수익을 더하여 i일에 시작한 상담이 끝나는 날의 최대 수익을 업데이트할 수 있습니다.
• 따라서 dp[end_date]의 값은 이미 저장되어있는 dp[end_date]와 profit(i-1일까지의 최대 수익)+meetings[i][1](i일의 상담 수익)을 비교하여 더 큰 값으로 갱신합니다.
• 그리고 마지막에는 dp[n]이 아닌 max(dp)를 출력합니다. 왜냐하면 for문을 한번만 사용하여 i일에 시작한 상담이 끝나는 날의 dp값만 업데이트되기 때문에 만약, 마지막 날에 끝나는 상담이 없다면 dp 값이 갱신되지 않습니다. 따라서 dp 배열의 최댓값을 print하여 최대 수익을 출력하도록 합니다.

 

🌱 정답 코드

# !/usr/bin/env python
#  -*- coding: utf-8 -*-
# boj 15486 퇴사2

import sys

input = sys.stdin.readline

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

# DP 풀이
profit = 0
for i in range(1, n + 1):
    end_date = i + meetings[i][0] - 1
    profit = max(profit, dp[i - 1])
    if end_date <= n:
        dp[end_date] = max(dp[end_date], profit+meetings[i][1])

print(max(dp))