문제
https://www.acmicpc.net/problem/14501
문제 풀이
- 이 문제를 풀 때는 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근하여 해결해야 한다.
- 나는 처음에 앞에서(왼쪽) 부터 해결하려고 했다가 헤맸는데 거꾸로 푸니까 쉽게 해결할 수 있는 문제였다.
그림 출처 : 이것이 취업을 위한 코딩테스트다 with python
1일 차에 상담을 진행한다고 해보자.
이 경우 3일에 걸쳐서 상담을 진행해야 한다.
-> 결과적으로 4일부터 다시 상담을 진행할 수 있다.
그러므로 1일 차에 상담을 진행하는 경우, 최대 이익은
1일차의 상담 금액 + 4일차 부터의 최대 상담 금액
이 된다.
따라서, 이러한 원리를 이용하여 뒤쪽 날짜부터 거꾸로 계산하며 문제를 해결할 수 있다.
즉, 뒤쪽부터 매 상담에 대하여
'현재의 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i]]'
을 계산하면 된다.
점화식
dp[i] = max(p[i] + dp[t[i] + i]]), max_value
dp[i] = i 번째 날부터 마지막 날 까지 낼 수 있는 최대 이익
max_value = 뒤에서부터 계산할 때, 현재까지의 최대 상담 금액에 해당하는 변수
소스코드
n = int(input()) # 전체 상담 개수
t=[] # 각 상담을 완료하는데 걸리는 기간
p=[] # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0] * (n+1) # 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)
UXUI Designer