[14501] 퇴사

import sys

N = int(sys.stdin.readline().strip())
reservation_list = []
for _ in range(N):
    T, P = map(int, sys.stdin.readline().split())
    reservation_list.append([T, P])



'''
dp 문제 - 상향식, 메모이제이션

1. 일단 N이 0인것부터 시작해서 N까지 최댓값을 찾을거임
2. 어디서부터 이어붙일지가 중요해서 상담을 끝낸 마지막날을 저장할거임 
    2-1. 이거 필요한가? 어짜피 index 이하일텐데.
    2-2. 결론은 저장할 필요없음.
3. 1 이상은 그 이하의 기록에서 붙여보면서 뭐가 최대가 되는지 볼거임
4. 근데 건너뛰고 수행하는게 제일 세면 어떻게함?
5. 건너뛰고 수행하는건 함수(5)에서 기록(2)에서 5번 index의 예약을 불러와서 붙여보고 계산하는게 동일함
6. Profit!
7. 근데 붙이는게 중요함 이게 뒤에 꼬리가 붙음

'''

consultation_result = [0 for _ in range(N)]
def doConsultation(reservation, max_date):
    T, P = reservation[max_date]
    if max_date == 0:
        v = 0
        if max_date + T -1 < N:
            #if v + P > consultation_result[max_date + T - 1]:
            consultation_result[max_date + T - 1] = v + P
    for cr_index in range(max_date):
        v = consultation_result[cr_index]
        if max_date + T -1 < N:
            if v + P > consultation_result[max_date + T - 1]:
                consultation_result[max_date + T - 1] = v + P


'''
doConsulation(0)인 경우 -> 
    T, P = 3, 10
    0 까지 돔 (), consultation_result[]를 순회함
        v = 0
        만약 0+(3-1) < 7 일 경우
            consultation_result[0 + (3 -1)] = v + P
doConsulation(1)인 경우 -> 
    T, P = 5, 20
    1 까지 돔 (0), consultation_result[]를 순회함
        v = consultation_result[인덱스] = 0
        만약 0+(5-1) < 7 일 경우
            v + P가 consultation_result[0 + (3 -1)] 보다 클 경우
                consultation_result[0 + (3 -1)] = v + P
'''

for n in range(N):
    doConsultation(reservation_list, n)

# print(consultation_result)
print(max(consultation_result))

 

DP 동적계획법 문제이다

 

동적 계획법은 중복해서 계산해야 되는 내용을 따로 분리해서 미리 계산해놓고 기억해놓는다 (메모이제이션)

그렇게 미리 계산해놓고 기억해 놓은 내용을 활용해서 더 큰 계산을 수행한다 (상향식 접근법)

 

사실 그렇게 다이나믹! 한것같진 않다...

 

이 문제에서는

할수 있는 상담날짜가 딱 하루인경우부터 시작해서 하루씩 늘려가며 최대 수익을 계산하고 저장해놓는다

 

맨처음에는 그리디한 접근법으로 생각해서 그 전 날짜의 최대값에서 한개씩 더해가면 되지 않을까 했는데

그렇게 할 경우 스킵하고 더 밸류가 좋은 상담을 해야하는 경우를 체크하지 못한다

 

그리고 마지막에 상담을 끝낸 날짜부터 이어붙여야 한다고 생각해서 상담을 끝낸 날짜를 같이 저장하려고 했는데,

이 경우에도 중간에 스킵하고 더 밸류가 좋은 상담을 해야 하는 경우를 체크하지 못할것같았다

 

설명이 힘들어서 클로드를 돌렸다

 

DP적 접근이 왜 필요했나?

처음엔 간단하게 생각했다. "오늘까지의 최대 수익 = 어제까지의 최대 수익 + 오늘 상담 수익". 하지만 이건 순차적으로만 생각하는 그리디 접근이었다.

문제는 상담이 여러 날에 걸쳐 진행된다는 점이다. 1일차에 3일짜리 상담을 시작하면 2일차, 3일차에는 다른 상담을 할 수 없다. 그런데 2일차에 훨씬 좋은 상담이 있다면? 1일차 상담을 포기하고 2일차 상담을 선택하는 게 나을 수도 있다.

 

DP로 사고 전환:

이 문제는 최적 부분 구조를 가진다. 즉, 전체 문제의 최적해가 부분 문제의 최적해들로 구성된다는 뜻이다.

그래서 생각을 바꿨다. "각 시점에서 끝나는 최적의 스케줄"을 미리 계산해두자.

1. 상태 정의: dp[i] = i번째 날에 마지막 상담이 끝났을 때의 최대 수익
2. 부분 문제: 각 상담을 선택했을 때, 그 이전 어떤 시점의 결과와 연결할 것인가?

전이 과정의 의미:

예를 들어 5일차에 시작하는 2일짜리 상담(6일차에 끝남)을 고려한다면:

• 0일차 결과와 연결: 0일차까지 최적 + 5일차 상담 → 1~4일차는 휴식
• 1일차 결과와 연결: 1일차까지 최적 + 5일차 상담 → 2~4일차는 휴식
• 2일차 결과와 연결: 2일차까지 최적 + 5일차 상담 → 3~4일차는 휴식
• 3일차 결과와 연결: 3일차까지 최적 + 5일차 상담 → 4일차는 휴식
• 4일차 결과와 연결: 4일차까지 최적 + 5일차 상담 → 바로 이어서

이 모든 경우 중 가장 좋은 것을 선택한다.

 

왜 이게 최적해를 보장하나?

최적 부분 구조 때문이다. 각 단계에서 이전의 모든 최적해를 고려하고, 이전 단계들이 이미 최적이라는 걸 보장받기 때문에 현재 단계에서도 최적을 만들 수 있다.

또한 메모이제이션을 통해 한 번 계산한 부분 문제의 결과를 저장해두므로, 중복 계산을 피하면서 효율적으로 해결할 수 있다. 중간에 건너뛰는 것, 연속으로 하는 것, 모든 패턴이 자연스럽게 포함된다.

 

최적 부분 구조를 잘 설명해준다

사실 이게 그리디한 접근법과 많이 헷갈리는것같다

 

클로드는 이렇게 설명해주고 있다

맞습니다! 정말 좋은 지적이에요.

헷갈릴 수 있는 지점:

DP에서도 결국 각 단계에서:

dp[i] = max(dp[0] + P, dp[1] + P, dp[2] + P, ...)

이렇게 **"지금 당장 최댓값"**을 선택하잖아요.

그러면 "이것도 그리디 아닌가?"라고 생각할 수 있죠.

핵심 차이는 "선택의 범위":

전통적인 그리디:

• 현재 상황에서 하나의 기준으로만 판단
• "가장 큰 수익", "가장 짧은 시간" 등 단일 기준
• 다른 가능성은 아예 고려 안 함

DP의 "지역적 최적 선택":

• 모든 가능한 이전 상태를 다 고려한 후 최적 선택
• 선택지가 훨씬 넓음 (모든 부분해)
• "어떤 이전 상태와 연결할까?"에 대한 전체 탐색

결국 관점의 차이:

• 그리디: "이 상담 자체가 좋아 보이니까 선택"
• DP: "이 상담을 모든 가능한 이전 상태와 연결해봤는데, 그 중에서 최고가 이거야"

그래서 DP를 "전역적 관점에서의 지역적 최적화"라고 볼 수도 있겠네요.

정말 예리한 관찰이었습니다! 이런 혼동이 생기는 게 자연스러워요.

 

 

좀 더 풀어봐야겠다...

그리고 실제로 푸는거랑 설명하는거랑 차이가 많이 난다는걸 알게됬다