[백준/Python]15486: 퇴사 2

문제

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

백준 문제집 - 0x10강 - 다이나믹 프로그래밍

 

알고리즘: 다이나믹 프로그래밍

---

풀이

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

문제 자체는 14501: 퇴사와 동일하다.

그래서 혹시나 하고 이전 풀이를 그대로 제출해봤더니 시간초과다.

저번처럼 이중 for문으로 하나하나 비교해가며 업데이트하면 바로 시간초과를 받는다.

 

중복 체크를 피하려면 역순으로 계산해야한다.

즉, dp[i] = i번째 날부터 퇴사일까지 얻을 수 있는 최대 금액을 나타내게 된다.

따라서 i번째날에 상담을 하지 않는다면, i+1번째 날의 최댓값을 가져와야한다.

역순이기 때문에 미래의 값으로 현재의 값을 채우는 구조가 된다.

그러므로 dp를 N+1만큼 생성 후 N-1부터 0번째 까지 순회한다.

(N만큼만 생성하는 방법도 있지만 직관적이지 않음.)

 

조건은 하나만 체크하면 된다.

현재 상담일자 i + 소요기간 Ti 가 N을 초과하는지 확인하고, 초과한다면 i+1날의 최댓값을 가져온다.

초과하지 않는다면 i번 상담을 잡을 수 있다는 뜻이므로 (현재 상담을 수행하지 않는 경우 dp[i+1], 수행하는 경우 Pi + dp[i번 상담이 끝난 후])를 비교하여 더 큰값으로 업데이트한다.

 

모든 순회를 끝내면 첫번째날부터 시작할 경우의 최댓값 dp[0]을 출력한다.

 

전체 코드

# ⭐ 시간 단축 요인: 튜플 사용, (time, pay)와 같이 언패킹
# 메모리: 252484KB / 시간: 2044ms
from sys import stdin


input = stdin.readline

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

dp = [0] * (N + 1)

for i in range(N - 1, -1, -1):  # 역순으로 순회
    time, pay = lst[i]
    if i + time > N:  # 상담 종료일이 퇴사일 이후
        dp[i] = dp[i + 1]
    else:
        # 현재 상담을 수행하는 경우와 수행하지 않는 경우 중 최댓값
        dp[i] = max(dp[i + 1], pay + dp[i + time])

print(dp[0])

참고로 tuple()대신 list()를 사용하고 time, pay 대신 lst[i][0], lst[i][1]로 사용했을때 → 메모리: 346424KB / 시간: 2832ms 였다...

생각보다 차이가 커서 놀랍다;;

덕분에 dp를 N만큼 생성했을때보다 더 효율적인 결과가 나왔다.

튜플, 언패킹 쌩유!