조금 더 어려운 다이나믹 프로그래밍 연습하기 -퇴사1,2-

1. 문제

 

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사

 

15486번: 퇴사 2 (acmicpc.net)

15486번: 퇴사 2

 

주어진 일정표에 상담기간과 해당 상담을 완료하면 얻는 이익이 주어진다.

 

N+1일에 퇴사할려고 할때, 그 전에 최대이익을 얻도록 상담을 끝내고 싶다.

 

가능한 최대이익을 구하는 프로그램을 작성해본다면..?

 

 

2. 풀이

 

예전에 푼 수영장 문제랑 비슷한줄 알았더니 조금 다른 문제더라

 

어렵다고 생각하지말고.. 할만큼 했으니까 조금이라도 생각은 해보면 풀리긴 하더라

 

dp를 먼저 정확하게 정의하고 시작해

 

dp[i]를 i일이 지나서 이 사람이 얻을 수 있는 최대이익이라고 정의하자.

 

일단 문제를 잘 읽어

 

n일에 끝나는게 아니야 n일까지는 상담을 해도 돼

 

 

 

즉 n일에 1일짜리 상담이 가능하다면, 그것은 선택가능하다

 

그러므로 dp[n+1]을 구하는게 목표다.

 

먼저 시간과 이익값을 리스트로 일단 받아

 

dp[n+1]을 구할거니까 dp배열은 0~n+1이 되도록 n+2까지 잡아주고

 

from sys import stdin

n = int(stdin.readline())

t_list = [0]
p_list = [0]

for _ in range(n):
    
    t,p = map(int,stdin.readline().split())

    t_list.append(t)
    p_list.append(p)
    
dp = [0]*(n+2)

 

 

다음에 1일부터 n일까지 순회를 할건데, dp[i]를 어떻게 구하냐?

 

예를 들어 1일차의 3일치 상담을 선택한다면, 언제 이익을 얻을 수 있는가?

 

1일,2일,3일까지 상담을하고 4일째 이익을 얻는다

 

2일차의 5일치 상담을 선택한다면?

 

2일,3일,4일,5일,6일까지 상담을 하고 7일째 이익을 얻는다

 

3일차의 1일치 상담을 선택한다면?

 

3일까지 상담을 하고 4일째 이익을 얻는다

 

그러므로 i일차의 t_list[i]일치 상담을 선택한다면...

 

t_list[i]+i일째 이익을 얻게된다

 

 

그러면 dp[t_list[i]+i]의 값은 어떻게 구하는가?

 

t_list[i]+i일째 최대이익은 어떻게 알수 있는가?

 

i일까지 얻은 최대이익이 dp[i]이고, i일차의 상담을 선택한다면 얻는 이익은 p_list[i]이다.

 

이거는 t_list[i]+i일째 정산받는다.

 

그러므로 t_list[i]+i일째 얻는 이익은 dp[i]+p_list[i]가 된다.

 

그런데 1~n일사이에 모든 상담을 검사하면서 t_list[i]+i일째 이익을 정산하는 경우가 여러개 있을 수 있으니까...

 

dp[t_list[i]+i]는 dp[t_list[i]+i]와 dp[i]+p_list[i]중 더 큰 값이 된다.

 

for i in range(1,n+1):
    
    dp[t_list[i]+i] = max(dp[t_list[i]+i],dp[i]+p_list[i])

 

여기까지 생각한것도 사실 훌륭하다.. 예전같았으면 하지도 못했을것 같은데

 

그런데 조금 더 생각해줘야한다

 

"또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다"

 

이 말은 6일차의 상담을 선택하면 6일,7일,8일,9일까지 상담하고 10일째 정산받는데

 

얘는 8일에 퇴사하니까 선택할 수 없다

 

7일차의 상담을 선택하면 7일,8일까지 상담하고 9일째 정산받는데, 8일에 퇴사하니까 선택할 수 없다

 

즉 정산받는날 t_list[i]+i가 n+1을 넘어가서는 안된다

 

for i in range(1,n+1):
    
    if t_list[i]+i <= n+1:
    
        dp[t_list[i]+i] = max(dp[t_list[i]+i],dp[i]+p_list[i])

 

 

여기까지 생각했다면 정말 더 훌륭하다

 

근데 이제 이렇게하면 문제가 뭐냐면...

 

dp[i]를 i일이 지나서 이 사람이 얻을 수 있는 최대이익이라고 설정해놨는데

 

단순히 저 점화식에 의해서만 구해본다면...

 

 

 

8일째 가져가는 돈은 0이 된다... 최대 이익은 45원임에도 불구하고..

 

이런 경우가 생기는건 1부터 순회하는데, 상담기간만큼 점프하다보니까 이전에 최대이익이 있는 경우가 있을 수 있다는것이다

 

이전날에 더 최대이익을 얻을 수 있는 경우가 있다면, 그런 경우를 선택해서 가져가야한다.

 

아주 심플하게 이런 경우가 있을 수 있겠지?

 

 

위의 경우 2일까지 순회했을때... 위와 같은 dp배열이 만들어지는데

 

dp[4]가 50이고 dp[5]가 30이다.

 

5일째에 30을 얻는다는 것은 무슨뜻일까? 

 

1일차의 3일짜리 상담은 선택하지 않고, 하루 넘긴다음에 2일차의 3일짜리 상담을 선택해서 30을 얻었다는 것이다.

 

하지만 이전까지 얻은 이익과 현재 얻을 수 있는 최대 이익을 비교해서, 이전 이익을 가져간다는 것은?

 

그러니까 5일째 최대 30인데, 4일치 이익이 최대 50이라서, 5일치 이익을 50으로 바꾼다는 것은 어떤 의미를 가지는 것일까?

 

그거는 2일차의 3일짜리 상담을 선택하지 않고, 1일차의 3일짜리 상담을 선택해서 50을 얻고, 하루는 그냥 넘긴다는 뜻이다

 

이렇게 하는게 더 최대거든

 

for i in range(1,n+1):
    
    if dp[i] < dp[i-1]:
        
        dp[i] = dp[i-1]
    
    if t_list[i]+i <= n+1:
    
        dp[t_list[i]+i] = max(dp[t_list[i]+i],dp[i]+p_list[i])

 

매 순회마다, 이전 이익이 더 크다면 현재 이익을 이전 이익으로 교체해준다.

 

여기까지 생각할 수 있다면 정말 발전했다.. (오래 걸리긴 했지만 자랑스럽다)

 

마지막으로 n일까지 순회한다면, 마지막 n+1일째 얻을 수 있는 이익은?

 

dp[n]과 dp[n+1]을 비교해서 dp[n]이 더 크다면, 그것을 취할 수 있도록 교체해주는 작업을 잊지말자

 

마찬가지로 이렇게 하는것 자체가, 어떤 상담은 선택하고 어떤 상담은 선택하지 않아서, 최대 이익이 되도록 만드는 작업이 숨어있다는것이지

 

from sys import stdin

#입력을 받는다
n = int(stdin.readline())

#인덱스 편의를 위해 1~n이 되도록 0은 미리 추가해놓는다. 
t_list = [0]
p_list = [0]

for _ in range(n):
    
    t,p = map(int,stdin.readline().split())

    t_list.append(t)
    p_list.append(p)

#n+1일에 퇴사하므로, n일까지는 상담이 가능하다.
#dp[n+1]을 구하는게 목표
dp = [0]*(n+2)

for i in range(1,n+1):
    
    #매 순회마다, 이전 날에 얻은 이익이 더 크다면 그것을 가져가야한다.
    #이 과정 자체가 어떤 상담은 선택하지 않고, 어떤 상담은 선택하는 효과를 준다.
    if dp[i] < dp[i-1]:
        
        dp[i] = dp[i-1]
    
    #정산받는 날은 t_list[i]+i이고, 이것이 n+1이내여야 상담 선택 가능하다.
    if t_list[i]+i <= n+1:
        
        #i일차의 상담을 선택해봐서, 최대이익이라면 교체해준다.
        dp[t_list[i]+i] = max(dp[t_list[i]+i],dp[i]+p_list[i])

#마지막 n까지 순회하고 나서 n+1일차에 가져가는 돈은...
#n일차 돈과 n+1일차 돈을 비교해서 최대이익 돈을 가져가도록 교체해준다.
#역시 이런 과정 자체가, 어떤 상담은 선택하고 어떤 상담은 선택하지 않는 효과를 준다.
if dp[n] > dp[n+1]:
    
    dp[n+1] = dp[n]

print(dp[n+1])