[완전 탐색] 백준 14501번 (파이썬) : 퇴사

 

date = int(input())
t = []
p = []
max_gain = []

for _ in range(date):
  ti, pi = map(int, input().split())
  t.append(ti)
  p.append(pi)

for _ in range(date + 1):
  max_gain.append(0)

for i in range(date-1, -1, -1):
  if t[i] + i > date:
    max_gain[i] = max_gain[i+1]
  
  else:
    max_gain[i] = max(max_gain[i+1], max_gain[t[i]+i] + p[i])

print(max_gain[0])

먼저 예제 입력을 따라 date 변수를 입력받아줍니다. 

그리고 퇴사 전 남은 날짜에 따라 상담 시간과 이익을 계속 받아줘야 하기 때문에 상담 시간과 이익 모두 배열로 생성해 줍니다. max_gain은 문제의 정답 출력에서 말하는 최대 이익을 출력하는 배열이다.

 

먼저 퇴사 전 스케줄을 받아줘야하기 때문에 for문으로 시간과 이익을 입력받고 모두 해당 변수에 해당하는 배열에 append 시켜줍니다.

두 번째 for문은 max_gain에 대한 것인데 위와는 다르게 한 칸 더 append 해주는 이유는 밑에 나오는 for문애서 알 수 있듯이 퇴사 일자가 넘어가는 경우를 고려하기 때문입니다. 만약 range를 date까지로 한다면 밑에 for문에서 if문에서 오류가 발생할 것입니다. 

마지막 for문의 경우에는 위에서부터 내려갑니다. if문의 조건은 해당 일자에 잡힌 상담의 개수가 퇴사일을 넘어가는 경우를 말하며 만약 넘기는 경우 해당 일자에는 상담을 하지 않고 다음으로 넘기는 방식입니다.

 

else문의 경우에는 다음날의 max_gain과 오늘의 max_gain 중 더 큰 값을 담는 방식입니다. 위에서부터 내려오기 때문에 더 늦을 날짜에 해당하는 max_gain이 먼저 도출됩니다. 그러면서 1일차(0번 인덱스)까지 내려가기 때문에 당연히 max_gain[0]이 가장 큰 값이 될 수 밖에 없는 것입니다. 요약하자면 max_gain[date-1]부터 한 칸씩 밑으로 비교하면서 max값을 업데이트하면서 0번 인덱스까지 도달하는 것이기 때문에 더욱 많이 업데이트된 max_gain[0]이 가장 큰 값인 것입니다.