[백준/Python]14501: 퇴사

문제

https://www.acmicpc.net/problem/14501
백준 문제집 - 0x10강 - 다이나믹 프로그래밍

 

알고리즘: 다이나믹 프로그래밍, 브루트포스

---

풀이

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

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

11055: 가장 큰 증가하는 부분수열 문제와 비슷하게 풀면 된다.
단, 이전 상담이 끝나야만 다음 상담을 진행할 수 있고 상담기간이 N(마지막 근무일)을 넘어가면 안된다.

 

먼저 N만큼의 dp를 생성한 후 첫째날의 상담 일정을 확인한다.
첫째날 상담의 소요기간이 N 이하라면 dp[0] = 첫째날 상담 보수로 할당하고, 넘어간다면 패스한다.

 

그 후 1일부터 N-1일까지 순회를 진행하며 dp를 업데이트한다.
현재 날짜의 상담 i를 기준으로 0 ~ i-1 일까지의 상담 j를 비교하며 날짜가 겹치지 않는 경우에만 업데이트한다.
즉 상담을 예약할 수 있는 조건은 두 가지다. 1) 현재 날짜 i + 상담기간 Ti 가 N 이하일것, 2) (현재 날짜 i - 이전 상담 날짜 j) < Tj 를 만족할것.

위의 예시 데이터로 살펴보자.
6일(인덱스상 5)의 상담을 기준으로 2일의 상담을 비교했을때, (i - j) = (5 - 1) = 4, Tj = 5 이므로 2일날의 상담을 예약해놓은 상태에선 6일날의 상담을 진행할 수 없다.
이런식으로 두 조건을 비교해가며 만족하는경우엔 (현재 상담을 선택할경우의 최댓값 dp[i], j일까지의 최댓값 dp[j] + 현재 상담의 보수 Pi) 중 더 큰 값으로 업데이트한다.
만약 2번 조건을 만족하지 못한다면 (현재 상담을 선택할경우의 최댓값 dp[i], 현재 상담의 보수 Pi) 중 큰 값을 선택한다.

 

전체 코드

# 메모리: 31120KB / 시간: 40ms
from sys import stdin


input = stdin.readline

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
# dp[i] = i번째 원소를 포함하는 값 중 최대값
dp = [0] * N

# 첫째날 상담의 소요기간이 N일 이하일때만 예약 가능.
if lst[0][0] <= N:
    dp[0] = lst[0][1]

for i in range(1, N):
    # (현재 날짜 i + i일 상담의 소요기간 > 마지막 근무날 N) 이면 쓰루.
    if i + lst[i][0] > N:
        continue
    for j in range(i):
        # (현재 날짜 - j일 < j일 상담의 소요기간)이라면 dp[i]와 현재 날짜의 상담 보수 중 더 큰것을 택함.
        if (i - j) < lst[j][0]:
            dp[i] = max(dp[i], lst[i][1])
        else:
            dp[i] = max(dp[i], dp[j] + lst[i][1])

print(max(dp))