[python] BOJ 백준 14501: 퇴사

1. 문제  

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

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

2. 입력   

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

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

3. 출력   

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

4. 해결방법   

DP알고리즘을 이용하여 풀어야 하는 문제이다. 완탐으로 푼다면 시간초과가 날 것이다. 코드는 정말 간단하지만 DP문제임을 알아차리지 못했다면 시간이 오래걸릴수도 있는 문제이다. 배열의 끝에서부터 탐색을 하면서 오늘의 일을 처리하고 받는 비용 + 일처리를 하는데 걸리는 날짜에 해당하는 비용 과 그냥 이후날의 비용중에 큰값을 저장하며 업데이트 해주어야한다. 단 주의할점은 처리기간이 배열의 크기보다 크면 안되므로 N보다 크다면 이후날의 비용을 그대로 저장해주어야한다. 

 

5) 구현코드       

n=int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

dp = [0 for i in range(n+1)]

for i in range(n-1,-1,-1):
    if i + graph[i][0] > n: #퇴사할 날보다 기간이 짧으면 
        dp[i] = dp[i+1] #그대로 저장 
    else: 
    #오늘의 일을 처리하고 받는 비용 + 일처리를 하는데 걸리는 날짜에 해당하는 비용
    #현재값
    #두 수중에 큰값을 저장 
        dp[i] = max(graph[i][1] + dp[i + graph[i][0]], dp[i+1])

print(dp[0])

 

⭐️난이도:  실버 3 ⭐️ 

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

14501번: 퇴사