[DP] 백준 14501 문제 풀이

이 문제는 생각한 것 보다 어려웠다.  DP로 풀어야겠다고 생각을 하고 짰는데 배열 1에서부터 시작하니 날짜 계산을 어떻게 해야할 지 감이 안왔다. 

그래서 상담잡는 순서를 마지막날에서부터 시작하였다. 

일단 상담을 잡을수 없는 날과 상담을 잡을 수 있는 날로 조건을 나눈다. 

 

1. 상담을 잡으면 퇴사일을 넘기는 경우

DP[i] = DP[i+1] 전날에 잡은 상담 가격 대입

2. 상담 잡을 수 있는 경우 

max(DP[i+1], DP[i+time[i]]+Price[i]) 전날에 잡은 상담가격과 (오늘상담가격+상담일지난후의 상담가격) 중 큰 값 

 

 

def main():
    n = int(input())
    max_price_list = [0 for _ in range(n + 2)]
    time_list = [0 for _ in range(n + 2)]
    price_list = [0 for _ in range(n + 2)]
    for day in range(1, n + 1):
        time, price = map(int, input().split())
        time_list[day] = time
        price_list[day] = price
        max_price_list[day] = price
    for day in range(n, 0, -1):
        if time_list[day] + day - 1 > n:  # 상담잡으면 퇴사일 넘길 경우
            max_price_list[day] = max_price_list[day + 1]
        else:
            max_price_list[day] = max(max_price_list[day + 1], price_list[day] + max_price_list[day + time_list[day]])
    print(max_price_list[1])


if __name__ == '__main__':
    main()