[백준 14501번] 퇴사

n = int(input())

data = []

for i in range(n):
    data.append(tuple(map(int,input().split())))

dp = [0] * 1006

for i in range(n-1,-1,-1):

    time = data[i][0]
    value = data[i][1]
    
    if (i+time) <= n:
        dp[i] = max(value+dp[i+time],dp[i+1])
    else:
        dp[i] = dp[i+1]

print(dp[0])

이번 문제는 각 날짜마다 정해진 상담 기간 Ti 상담 금액 Pi가 주어졌을때, N일 동안 최대한 수익을 많이 낼 수 있도록 날짜를 선택하는 문제이다.

 

처음에 이 문제를 접했을 때는 기간과 금액이라는 2가지 값이 주어져서 DP 테이블로 2차원 리스트를 활용해야 하는 줄 알았는데, 곰곰히 생각해본 결과 1차원 리스트로도 충분히 풀 수 있다는 것을 깨달았다.

 

대신에 DP 리스트를 앞에서부터 채우는 것이 아니라 뒤에서부터 채우는데, 일단 현재 날짜로 부터 소요되는 상담 기간(i + time)이 남은 기간 N보다 작거나 같은 경우에만 값을 비교할 수 있다.

 

만약에 현재 날짜로부터 상담이 가능한 경우, 현재 날짜로부터 상담을 진행했을 경우(value + dp[i+time])와

현재 날짜에 상담을 진행하지 않는 경우(dp[i+1])를 비교하여 더 큰 값을 DP 테이블에 저장하는 방식으로 풀이할 수 있다.

 

DP 알고리즘을 새로운 방식으로 사용해볼 수 있었던 좋은 문제였다 :)