N일동안 상담을 진행하여 최대 수익을 내는 값을 찾는 프로그램 짜기.
각일 수 별 상담소요일자와 받을 수 있는 금액이 있다.
풀이 경로:
최근에 풀었던 문제들과 풀이 경로가 비슷하다는 생각이 들었다. 그래서 2차원 테이블을 사용해보았다.
0번째 인덱스에는 상담소요일자, 1번째 인덱스에는 금액.
생각한 예외: 우선 상담일자를 넘어가는 경우 Ti+i가 상담일자를 넘어갈 때를 고려했다.
그래서 계속 갱신해가는 방식을 사용해 보았는데, 오류가 있었다.
첫번째로 앞에서 부터 진행하다 보니 갱신하는 방식으로는 풀 수 없었다.
왜냐하면 상담소요 일자만큼 건너뛰면서 값을 더해가야 했는데, 갱신해버리면 다양한 경우의 수를 활용못해서
말도 안되는 방법이었다.
그리고 Ti+i가 N-1을 넘지 않는 조건으로만 하다보니, 상담일자상으로 넘어가는 것을 구현하지 못했다.
대망 ㅠ
풀이
뒤에서 부터 푸는 방식이었다. 시간,금액, dp테이블을 전부 따로 둔다.
i번째 날에서 현재 날짜에서 상담을 했을 때 기간을 넘기는지 여부로 조건을 주어
현재까지의 최대금액과, 오늘 상담을 했을 때 금액+상담을 하고 지난 다음 날짜에서의 최대금액중
큰 금액을 max_value로 선택한다. 이 부분이 여러가지 선택의 경우의 수중 최대 금액인 경우를
정해주는 과정이다. 그 후 max_value 갱신.
뒤에부터 푸는 방식은 생각도 못했따.
풀이를 보니 한 케이스에서 원리를 찾아서 점화식을 만들어냈다.
아니면 그냥 하나의 관점이라고 볼 수도 있다.
#일하는 날짜 N 입력받기
n=int(input())
#시간, 금액 나눠서 입력 받기
t=[]
p=[]
# dp테이블을 따로 주었다 . 뒤에서 부터 해결할 거기 때문에 초기화 필요
#dp[i] = i번째부터 끝까지 낼 수 있는 최대 이익
dp=[0]*(n+1)
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:# n-1이 아닌이유는 n이 7일때 7일차는 상담기간이 6과 같으니까.
dp[i]=max(p[i]+dp[time],max_value)
max_value=dp[i]
#상담이 기간을 넘어가면
else:
dp[i]=max_value
print(max_value)