[백준] 14501. 퇴사 Python

문제 링크 : 14501. 퇴사

14501번: 퇴사

풀이 코드 : GIthub

 

문제

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

오늘부터 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이다.

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

 

풀이

풀이방법이 생각나지 않아 아래 블로그를 참고했다.

https://great-park.tistory.com/48

[BOJ/백준] 14501번 퇴사 (Python 파이썬)

생각보다 간단한 DP문제였다.

 

먼저 문제에 있는 예시의 표를 DPlist로 나타내면

 

위와 같이 된다.

여기서 맨처음 상담부터 DP를 채워나간다.

 

 

맨 처음 상담은 현재 아무 상담도 하지 않았으므로 아무 보상도 없고 그 다음에 지금 상담을 하면 3일 뒤에 보상을 10 얻는다.

이를 기록한 뒤 나머지는 아무 상담도 안한 것으로 기록한다.

 

 

그 뒤 다음 상담은 1일차에 보상 합은 없고 5일뒤에 20의 보상을 얻는다. 그래서 5일뒤에 20의 보상을 업데이트 하는데 

현재 6일에 보상합이 10이였으므로 현재 20의 보상으로 업데이트한다. (만약 10보다 작았으면 업데이트 하지 않는다.)

 

 

그 다음 상담은 역시 보상 합은 없고 1일 뒤 10의 보상을 얻는다. 하지만 이미 3일차의 보상 합이 10 이므로 업데이트 하지 않는다.

 

 

다음 상담은 현재 보상 합이 10이고 1일 뒤에 20의 보상을 주므로 1일뒤 보상이 30이 된다. 

4일차의 보상이 10이므로 보상이 더 큰 30으로 업데이트된다. 

그 후 상담일들도 모두 30보다 보상 합이 작으므로 30으로 업데이트 한다.

 

 

다음 상담은 현재 보상 합이 30이고 2일 뒤에 15의 보상을 주므로 2일뒤 보상의 합이 45이 된다.

6일차의 보상이 30이므로 보상이 더 큰 45으로 업데이트된다. 

그 뒤는 퇴사일 이므로 값이 업데이트 되는 것은 없다. 

 

 

마지막 5, 6일의 상담은 이미 퇴사일을 넘어가버려 계산할 필요가 없다.

 

그렇다면 마지막 근무일인 6일의 보상 합인 45가 최종 정답이 된다.

 

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

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

for i in range(N):
    for j in range(i+input_list[i][0], N+1):
        if dp[j] < dp[i] + input_list[i][1]:
            dp[j] = dp[i] + input_list[i][1]

print(dp[-1])