2021.2.28 [백준] 퇴사

다이나믹 프로그래밍 알고리즘

 

 

Q

 

www.acmicpc.net/problem/14501

14501번: 퇴사

 

A

 

다이나믹 프로그래밍으로 푸는 것은 점화식 세우기가 가장 중요하다. 

 

코드

 

n = int(input())
array = list(list(map(int, input().split())) for _ in range(n))

d = [0]*16 #DP 테이블 초기화

for i in range(n):
    if i + array[i][0] <= n: #해당 날짜 + 해당 날짜에 업무 걸리는 시간이 N을 초과하지 않는다면
        d[i] = array[i][1] #d를 해당 날짜 이익으로 설정
        for j in range(i): #0부터 해당 날짜까지의 기간
            if j + array[j][0] <= i: #똑같이 조건 세우기
                d[i] = max(d[i], d[j]+array[i][1]) #d는 해당날짜 이익과 그 전까지의 이익 더한거 중 최댓값
                
print(max(d)) #어느 날짜에서 마지막으로 업무보는 것이 제일 큰 값이 되는지 max로 확인