https://www.acmicpc.net/problem/14501
import sys
# with open("./data.txt", "r") as file:
# def input():
# return file.readline().strip()
def input():
return sys.stdin.readline().strip()
N = int(input())
# N+1일째 되는날까지 금액 계산이 필요하기 때문에.
dp = [0] * (N+1)
days = [0] * (N)
moneys = [0] * (N)
for i in range(0, N):
T, P = map(int, input().split())
days[i] = T
moneys[i] = P
# N+1일째 되는날 완료되는 상담이 있는지 확인하기 위해서 N+1
for i in range(N+1):
arr = []
for k in range(0, i):
if(k + days[k] <= i):
# 상담 완료 시점에
# 상담 시작일 금액 + 상담 시작일까지 모아뒀던 돈
arr.append(moneys[k] + dp[k])
if(arr):
dp[i] = max(arr)
else:
dp[i] = dp[i-1]
print(max(dp))
워매 3~4시간은 걸린 것 같다. (포기하고 싶었지만 견뎌냈다..)
약간 변형이 들어간 DP 문제같다.
하면서 헷갈리는게 너무 많았기에 복습하는 차원으로 로직을 설명해보자.
먼저 각 날마다 최고 수익을 저장하기 위한 DP 배열을 만들어주는데
N+1일 째 되는날 퇴사를 하기 때문에 N+1로 배열을 선언해주자.
dp = [0] * (N+1)그리고 날짜 + 상담소요일이 오늘보다 작거나 같은것들만 찾아주자.
그래야 오늘 이전의 최고 수익을 찾을 수 있다.
if(k + days[k] <= i):맨 처음에는 아래처럼
if(k + days[k] == i):
날짜+상담소요일이 오늘인것들 중에서만
찾아야 하는거 아닌가? 생각했지만
굳이 오늘이 아니어도 상관없다.
어제, 혹은 이틀전이라도 오늘 이전에
번 가장 높은 수익을 알고싶은 것이기 때문에
==가 아니라 <=가 맞다.
if(k + days[k] == i):
아무튼 위 조건식을 만족한다는건 상담이 끝났다는 얘기가 된다.
상담이 끝났으므로 상담비용 + 상담종료일까지 모아뒀던 최고 금액을
계산해주자.
그리고 오늘 할 수 있는 상담이 없으면
어제 상담비용을 그대로 가지고 있어주면 된다.
끝
어려워
한-줄