14501-백준-퇴사

1. 문제 출처

https://www.acmicpc.net/problem/14501

14501번: 퇴사

2. 풀이

동적 계획을 사용하여 구하였다..

 

# # 다이나믹 프로그래밍
# # Botton_top 방식
# 입력 받기
n = int(input())

T = [0]*n
P = [0]*n
for idx in range(n):
    T[idx],P[idx] = map(int,input().split())
results = [0]*(n+1)
def solution():
    #  N 번 반복한다.
    for day in range(n):
        # 상담 종료날
        end = day + T[day] 
        # 상담 종료날이 n+1보다 작거나 같으면
        if end <= n:
            # 첫날이 아니면
            if day !=0:
                # 해당 날에 이미 저장되어 있는 값과 비교하여 더 큰값을 넣는다.
                results[end] = max(max(results[:day+1])+P[day],results[end])
            else:
                results[end] = P[day]
    # 결과값 출력(상담을 어느날에 그만해야 최대 값인 것을 모르므로 결과들의 최대값을 출력)
    print(max(results))
            
solution()            
# 퇴사할 회사라도 있음 좋겠다..