[백준 14501번] 파이썬 - 퇴사

백준 14501_퇴사

14501번: 퇴사

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

# 조건

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

• 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 ≤ 15)이 주어진다.
• 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

# 접근 방법

• DP를 이용해서 풀어주면 될 것 같다.
• N 크기의 DP를 사용해주며 현재 날짜에서 Ti를 더했을 때 초과되지 않는 경우만 기록해준다.
• DP에 기록하는 방법은 현재날짜 이전의 값 중 최댓값을 뽑아서 현재날짜 + Ti에 기록해준다.
• 이후 마지막에 max(DP)를 출력해준다.

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

N = int(input())  

record = [[] for _ in range(N+1)]  
dp = [0] * (N+1)  

for i in range(1, N+1):  
    a, b = map(int, input().split())  
    if a + i -1 <= N:  
        dp[i+a-1] = max(max(dp[:i]) + b, dp[i+a-1])  

print(max(dp))