[코드트리] 외주 수익 최대화하기

Python3

문제

외주 수익 최대화하기

키워드

• 백트래킹

문제 풀이

문제 요구사항

n일 수익을 최대화 하려고 한다.
각 작업은 수행 완료하는데 걸리는 기한 t와 이를 완료 했을 때의 수익 p가 주어진다.
두 개 이상의 작업은 동시에 수행할 수 없으며, 휴가 기간(n+1일) 이후로는 일을 할 수 없다고 할 때 외주 수익의 최대값을 출력하는 프로그램.

변수 및 함수 설명

• n: 휴가 일수 1≤n≤15
• dp: 외주 수익을 저장하는 리스트
• arr: 각 일자에 수행할 수 있는 외주 작업의 기한인 t와 수익 p가 저장되는 2차원 리스트
  1≤t≤5, 1≤p≤1,000

풀이

백준 # 14501 퇴사 문제이다.

일을 수행할 경우와 수행하지 않을 경우로 나누어 생각해야 한다.

• 선택할 경우,
  dp[i+t[i]] + p[i] 가 된다.
• 선택하지 않을 경우,
  dp[i+1] 을 넣는다.

해당 값을 비교하여 더 큰 값을 dp에 저장한다.

그러나 소요 시간이 휴가 일수를 넘어가면, 아예 선택할 수가 없으므로 dp[i+1]을 dp에 넣는다.

top-down 방식으로 내려오면서 배열의 첫 번째에 가장 큰 원소가 저장된다. 해당 값을 출력해주면 된다.

최종 코드

n = int(input())

dp = [0 for _ in range(n+1)]
arr = [list(map(int, input().split())) for _ in range(n)]

for i in range(n-1, -1, -1):
    if i + arr[i][0] <= n:
        dp[i] = max(dp[i+arr[i][0]] + arr[i][1], dp[i+1])
    else:
        dp[i] = dp[i+1]

print(dp[0])

피드백