[백준 14501] 퇴사

www.acmicpc.net/problem/14501

14501번: 퇴사

---

접근

뒤에서부터 접근하고자 했다. 아직까지 DP의 개념을 완벽하게 이해하고있지 않아 뒤에서부터 어떻게 메모이제이션을 진행할지 감이 잡히지 않았다. 

그래서 다음과 같이 생각하기로 했다. 뒤에서부터 경우의 수에 따라 최댓값을 구하자.

즉 뒤에서부터 진행하면서 해당 날짜에 상담을 했을 때와 안했을 때의 수익 중 최댓값을 채워나간다.

 

이러한 개념으로 현재 날짜에 상담을 한다면 T일 후에있는 상담을 할 수 있기 때문에 두 개의 수익을 더하고 현재 날짜에 상담을 안한다면 다음 날 상담을 하게되므로 이 두 개의 경우의 수 중 최댓값을 채워나가도록 한다.

 

구현

상담스케줄을 info에 저장한다.

N = int(input())
info = []
for _ in range(N):
    info.append(list(map(int, input().split())))

 

메모이제이션을 할 리스트인 dp를 생성한다. 이때 0으로 초기화된 길이 16개인 리스트로 생성을 하는데 N의 최댓값은 15이다. 0~14인덱스에 0이 채워지고 14일에서 하루짜리 상담을 하는 것을 고려하여 한 개 더많은 리스트를 선언하여 나중에 현재상담했을 때 정확히 마지막 날인 경우에 사용한다.

dp = [0 for _ in range(16)]

 

뒤에서부터 탐색을 진행한다. 현재 날짜인 day에 상담을 했을 때의 수익 p와 상담기간 t를 활용한다.

상담을 했을 때 마지막 날을 넘어서고 현재 날짜가 마지막날이 아니라면 다음 날 상담의 최대수익을 현재 날짜에 대입한다.

 

현재날짜에 상담을 하여 정확히 마지막 날에 끝난다면 현재 수익과 다음 날의 수익을 비교한다. 해당 날에 상담을 하면 이후의 상담은 진행하지 못하기 때문이다.

 

위의 경우가 아니라면 현재 상담을 했을 때 다음 상담 일의 최댓값과 더하는 것과 다음 날 상담의 수익과 비교하여 최댓값을 현재 날에 대입한다.

for day in range(N-1, -1, -1):
    t = info[day][0]
    p = info[day][1]

    if day+t > N:
        if day != N-1:
            dp[day] = dp[day+1]
        continue

    if day+t == N:
        dp[day] = max(p, dp[day+1])
    else:
        dp[day] = max(p+dp[day+t], dp[day+1])