문제 링크

퇴사

문제 설명

백준이는 N+1일째 퇴사를 하려고 한다. 남은 N일간 많은 상담을 해서 그만두기전에 돈을 최대로 벌려고 하는데,
i일의 상담은 해결하는데 Ti일이 걸리고, Pi만큼 벌 수 있다. 예를 들어 5일째의 상담은 해결하는데에 이틀이 걸리고, 15를 번다. N+1일째는 퇴사하고 없으니 상담을 할 수 없다. 상담을 적절히 해서 백준이가 벌 수 있는 최대 수익은 ??

문제 풀이

시도 1 - 브루트포스 (재귀 이용)

i일에서 백준이가 할 수 있는 선택은
1. 오늘 상담 하기
2. 오늘 상담 하지 말기
두가지이다. 각각 두가지 경우에 대해서 재귀를 돌면서 해당 일에 상담을 한 경우/하지 않은 경우 얻을 수 있는 수익을 구한다.

import sys

input = sys.stdin.readline

N = int(input())
time = []
profit = []
answer = 0
for _ in range(N):
    t, p = map(int, input().split())
    time.append(t)
    profit.append(p)

def get_profit(day, total_profit):
    global answer
    # N일까지 끝내기 가능
    if day == N:
        answer = max(answer, total_profit)
        return
    # N일까지 끝내기 불가능
    if day > N:
        return
    # 오늘 일 하는 경우
    if day + time[day] <= N+1:
        get_profit(day+time[day], total_profit+profit[day])
    # 오늘 일 안하는 경우
    if day + 1 <= N+1:
        get_profit(day+1, total_profit)

get_profit(0, 0)
print(answer)

시도 2 - dp 이용

dp는 항상 어렵다...... https://pacific-ocean.tistory.com/199 님 풀이를 참고했다.
i번째 날 부터 N일까지 낼 수 있는 최대 이윤은
1. i번째 날 일 한 경우 : 현재까지의 이윤 + time[i]일뒤의 이윤
2. i번째 날 일 안한 경우 : i+1일의 이윤
중 큰 값이다.
점화식으로 표현하면,
max_profit[i] = max(pay+max_profit[i+time[i]], max_profit[i+1])
핵심은 뒤에서 부터 dp

import sys

input = sys.stdin.readline

N = int(input())
time = []
profit = []
dp = [0]*(N+1)
answer = 0
for _ in range(N):
    t, p = map(int, input().split())
    time.append(t)
    profit.append(p)

for i in range(N-1, -1, -1):
    #  남은 기간보다 상담일이 긴 경우
    if time[i] + i > N:
        #해당 일의 상담은 x
        dp[i] = dp[i+1]
    else:
        #오늘 상담할 수 있는 경우 : 오늘 상담 안한 경우와 한 경우중 최대
        dp[i] = max(dp[i+1], profit[i]+dp[i+time[i]])
print(dp[0])