[백준 15486번] 파이썬 - 퇴사2

백준 15486 - 퇴사 2

시간 제한 2초, 메모리 제한 512MB

# 조건

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

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

 

---

• 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다.
• 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
• 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
• 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다.
• 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
• 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
• 퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
• 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다.
• 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

• 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

# 접근 방법

• 14501 퇴사 문제와 N의 범위만 다르고 동일하다.
  • 즉, 브루트 포스가 아닌 dp를 활용해주며 dp 배열의 갱신을 효율적으로 해주어야 한다.
  • 14501 문제의 경우 dp 갱신을 리스트 슬라이싱을 사용해주었지만 현재는 범위가 1,500,000까지 가능하므로 불가능하다.
• dp의 크기는 N+1개로 만들어 준 후, 1부터 N까지의 반복문을 돌려준다.
• 오늘 날짜 상담에 걸리는 시간과 비용을 day, pay에 저장 해주고 day -= 1을 하여 상담이 완료되는 날짜로 변경해준다.
• 우선, 오늘 날짜와 오늘 하는 상담에 걸리는 시간을 더한 값이 N보다 작다면
  • dp[i+day] = max(dp[i+day], dp[i-1] + pay)
  • 상담이 완료되는 날짜에 기록된 값과, 어제까지 벌어들인 비용 + 오늘 상담에서 받는 비용 중 큰 값으로 갱신해준다.
• 이후, dp[i] = max(dp[i], dp[i-1])를 통하여 오늘까지 벌 수 있는 최대 비용을 계속 갱신해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def solve():  
    N = int(input())  
    schedule = [[0, 0]]  
    for _ in range(N):  
        a, b = map(int, input().split())  
        schedule.append([a, b])  

    dp = [0] * (N+1)  
    for i in range(1, N+1):  
        day, pay = schedule[i]  
        day -= 1  
        # 상담이 완료되는 날짜에 받는 최대 비용 갱신해주기  
        if i + day <= N:  
            dp[i+day] = max(dp[i+day], dp[i-1] + pay)  
        # 오늘까지 벌 수 있는 최대 비용 갱신해주기  
        dp[i] = max(dp[i], dp[i-1])  
    print(dp[-1])  
solve()