문제

풀이

풀이 아이디어

$dp[i] = max(p[i] + dp[t[i]+i]], max\_value)$

• dp[i]=i번째 날부터 마지막날까지 낼 수 있는 최대의 이익
• max_value = 뒤에서부터 계산할때, 현재까지의 최대 상담 금액에 해당하는 변수

뒤쪽부터 거꾸로 매 상담에 대하여 (현재 상담 일자의 이윤 p[i] + 현대 상담을 마친 일자부터의 최대 이윤 dp[t[i]]+i) 를 계산. 이후 계산된 각각의 값 중에서 최댓값을 추력

느낀점

요즘 알고리즘 풀때마다 느끼는건데
요상하고 내가 상상도 못한 기발한 알고리즘으로 짠! 하고 푼다기보다
기본은 모든 경우를 계산하는 것이고,
거기서 어떤 알고리즘으로 개선을 시키느냐의 문제인것 같다는 생각을 했다.
DP도 계산을 부분으로 쪼개고, 쪼갠 부분을 재활용해서 개선시키는거지 그렇게 거창하게 점화식!! 새로운 !! 수학!! 은 아닌 것 같다능.. (머쓱)

풀이

제출 코드

n = int(input()) # 전체 상담 갯수
t = []
p = []
dp = [0] * (n+1) # dynamic programming을 위한 1차원 dp 테이블 초기화
max_value = 0 #뒤에서부터 계산할때, 현재까지의 최대 상담 금액에 해당하는 변수

for _ in range(n) :
	x, y = map(int, input().split())
	t.append(x)
	p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n-1, -1, -1) :
	time = t[i] + i
	# 상담이 기간 안에 끝나는 경우
	if time <= n :
		# 점화식에 맞게, 현재까지의 최고 이익 계산
		dp[i] = max(p[i] + dp[time], max_value)
		max_value = dp[i]
	# 상담이 기간을 벗어나는 경우
	else :
		dp[i] = max_value

print(max_value)

이해를 위한 출력용 코드