14501: 퇴사

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

14501번: 퇴사

설명

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램 계산하자. 오늘부터 N+1 일째 되는 날 퇴사하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 따라서 하루에 하나씩 서로 다른 사람의 상담을 잡아 놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어 져 있다. 

핵심 아이디어

• 다이나믹 프로그래밍은 큰 문제를 작은 부분으로 나누고, 그 작은 부분 문제들이 반복되는 것을 이용하여 풀어 가는 방법이다. 모든 작은 문제들을 단 한번만 풀어야 하며, 그 결과를 어딘가 기록해 둠으로써 재사용한다.
• 부분 문제를 푸는 순서에 따라서 Top-Down, Bottom-up으로 나뉜다. 
• 부분 문제 풀이를 기록할 DP 테이블을 생성한다. 
• dp에는 i 번째 일까지 했을 때 얻을 수 있는 최대 수익이 기록된다. 따라서 최종적으로 리스트의 가장 마지막 값을 출력하면 된다. 

코드 구현

schedule에는 각 인덱스마다 [상담 기간, 비용]이 담기게 된다. 그리고 이중 반복문을 살펴보면,

1. 'i번째까지 일했을 때 얻을 수 있는 최대 수익'을 계산하기 위한 i를 기준으로
2. j는 i번째 날에 상담을 진행했을 때, '상담이 가능한 모든 날짜', 즉 i + '상담 기간'부터 마지막 날까지 입니다. 
3. 그리고 j를 기준으로 상담을 진행했었을 때 얻는 최대 수익을 dp[j]에 저장하도록 합니다. 

# 풀이 1

import sys
input = sys.stdin.readline

# 남은 기간 동안 일할 날짜 입력받기
n = int(input())
# [상담기간, 비용] 각각 입력받기
schedule = [list(map(int, input().split())) for _ in range(n)]
# print(schedule) 
# [[3, 10], [5, 20], [1, 10], [1, 20], [2, 15], [4, 40], [2, 200]]

# dp 테이블 초기화, i번째 날짜까지 일했을 때 얻을 수 있는 최대 수익 기록
dp = [0] * 16

for i in range(n): # 0 ~ n-1
    # 상담 시작 날(i) + 상담 기간부터 마지막 날까지 
	for j in range(i+schedule[i][0], n+1):
    	# 최대 수익이 더 작다면 최댓값으로 갱신한다.
        if dp[j] < dp[i] + schedule[i][1]:
            dp[j] = dp[i] + schedule[i][1]
print(dp)
# [0, 0, 0, 10, 30, 30, 45, 45, 0, 0, 0, 0, 0, 0, 0, 0]
print(max(dp))

i + schedule[i][0] 은 상담 시작일 i에 상담 기간 schedule[i][0]을 더한 값이다. 따라서 이는 상담이 끝나는 날짜는 나타 냅니다. 예를들어, i = 0이고 schedule[i][0]은 [3, 10]에서 3일 이므로 이 상담은 0+3으로 상담이 끝나는 날짜는 3일 입니다. i=1일 때는 [5, 20]이고 1+5=6으로 6일에 상담이 끝나게 됩니다. 또 i = 2 일때는 [1, 10]이 므로 2+1=3으로 상담이 3일 끝나게 됩니다

 

# 풀이 2

dp = [0] * (n+1) # 이렇게 초기화하고
#마지막에 배열의 마지막 원소를 출력하도록 하자
print(dp[-1])