[백준/Python] 15486번 퇴사2

월요일의 일 하기 싫은 마음을 담아서 퇴사2를 풀어봅시당.

도망가자 (출처: google)

 

-문제

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

15486번: 퇴사 2

 

-풀이

접근

백준님이 퇴사를 하려고 한다.

퇴사 전 한끝을 태우기 위해 최대로 상담을 땡겨 돈을 벌려고 한다.

결국 마지막 날까지 벌 수 있는 돈의 최대값을 구하는 것이다. 

첫날부터 주어지는 정보를 가지고 DP를 이용해 마지막 날까지 벌 수 있는 돈의 최대값을 구하자.

 

문제의 일반화

 

dp라는 각 날짜까지 벌 수 있는 돈의 최대값을 저장하는 리스트를 정의하고 몇몇 예시를 넣어보며 일반화를 시켜보죠

예제를 보면, 첫날(i)에 시작할 수 있는 상담은 총 3일이 걸리므로 3(time)일에 끝나고 이 상담을 통해 10(pay)을 벌 수 있어요.

그렇기에 dp[3] = dp[0] + 10이라고 할 수 있죠.

 

두번째 날에 대해서는 

dp[6] = dp[1] + 20으로 정리가 가능해요.

 

물론 이미 dp[6]에 다른 숫자가 자리를 차지하고 있다면 대소 비교를 통해 큰 값으로 교체해주어야 겠죠?

 

일단 두번정도의 간단한 시도를 통해서 알 수 있었던 것은 n개의 줄에 거쳐 주어지는 정보들로 dp리스트를 아래와 같은 게산을 통해 채워 넣을 수있다는 거에요..

 

dp[i + time - 1] = dp[i - 1] + pay

 

input을 한줄 한줄 스캔하며 i가 늘어갈 때마다 i - 1보다 작은 인덱스의 값들은 참고하지 않고 내버려 둔다는 것이죠.

그래서 저는 i - 1의 위치에다가 지속적으로 최댓값을 업데이트 해주어서 중복되는 연산을 없앴어요.

(소스코드를 같이 보시면 이해가 훨씬 편합니당)

 

근데 이러한 제 방법이 결국에는 최댓값을 정점에 위치시키고 새로운 값이 들어올 때마다 업데이트하는 힙과 비슷해서 힙을 이용한 풀이도 시도해보시면 좋을거 같아요!

 

-소스코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (n + 1)

for i in range(1, n+1):
    time, pay = map(int, input().split())
    a = i+ time -1
    if i != 1:
        dp[i-1] = max(dp[i-1], dp[i-2])
    if a <= n:
        dp[a] = max(dp[i-1] + pay, dp[a])
    
        
print(max(dp))