[Python] 백준 14501번 : 퇴사 (S4)

#문제

www.acmicpc.net/problem/14501

14501번: 퇴사

#풀이 & 학습한 내용

시작과 종료일이 있고, 각각의 수익이 다른 상담들 중에서 총 수익을 최대화하는 문제입니다. 종료일 기준으로 오름차순 정렬한 후에, dp[k]를 "k일까지의 최대이익"으로 정의하여 dp리스트를 앞에서부터 채워나갑니다. 그리고 dp[N]이 N일까지의 최대이익이므로 정답으로 출력합니다.

 

#소스코드

N=int(input())
consults=[] #상담들 저장하는 리스트
dp=[0]*(N+1) #★dp[k]: k일까지의 최대이익

for i in range(N):
  one_consult=[i+1]+list(map(int,input().split()))
  one_consult[1]=one_consult[0]+one_consult[1]-1
  if one_consult[1]<=N:
    consults.append(one_consult)
#[시작일, 종료일, 수익]으로 리스트에 모두 넣어줌
consults.sort(key=lambda x:x[1]) #종료일 기준 오름차순 정렬

temp=0
for consult in consults:

  for j in range(temp+1,consult[1]): #dp의 중간에 비워진 부분을 채워주기 위해
    dp[j]=dp[j-1]

  dp[consult[1]]=max(dp[consult[1]], dp[consult[1]-1], dp[consult[0]-1]+consult[2])
  temp=consult[1]

if temp!=N: #N일차까지 dp가 채워지지 않고 끝났을 때
  for j in range(temp+1,N+1):
    dp[j]=dp[j-1]

print(dp[N])

 

github.com/HoYoungChun/Algorithm_PS/blob/master/Dynamic_Programming/BOJ_14501.py

HoYoungChun/Algorithm_PS