[Python/Codetree] 외주 수익 최대화하기

https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit/submissions?page=1&pageSize=20&order=tier 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

n일의 휴가 동안 외주 개발을 하여 수익을 최대화 하려고 합니다. 수행할 수 있는 외주 작업이 하루에 한 개씩 있고, 각 외주 작업은 수행 완료하는데 걸리는 기한 t와 이를 완료 했을 때의 수익 p가 주어집니다. 두 개 이상의 외주 작업은 동시에 수행할 수 없으며, 휴가 기간 이후로는 일을 할 수 없다고 할 때 외주 수익의 최대값을 출력하는 코드를 작성해보세요.

예를 들어 n=3 이고 외주 작업이 다음과 같이 주어진 경우를 생각해봅시다.

1,2번 외주를 같이 하게 된다면 일해야하는 기간이 겹치게 되어 불가능합니다.

1,3번 외주를 같이 하게 된다면 겹치지 않게 일을 할 수 있고, 총 25 만큼의 돈을 얻게 됩니다.

2번 외주만 하게 된다면 26 만큼의 돈을 얻게 됩니다.

입력 형식

첫 번째 줄에는 n이 주어지고,

두 번째 줄부터 n+1번째 줄까지는 각 일자에 수행할 수 있는 외주 작업의 기한 t와 수익 p가 공백을 사이에 두고 주어집니다.

• 1≤n≤15
• 1≤t≤5
• 1≤p≤1,000

출력 형식

가능한 외주 수익의 최대값을 출력합니다.

풀이

Code

import sys
input = sys.stdin.readline

ans = 0
# 1. 백트래킹 함수 정의
def backtrackig(idx, cost) :
    global ans 
    # 1-1. 종료 조건
    if idx >= n : 
        # 마지막 인덱스에 도달한 경우
        if idx == n :
            ans = max(ans, cost)
        return
    # 1-2. 해당 외주를 하지 않는 경우
    backtrackig(idx + 1, cost)
    # 1-3. 해당 외주를 하는 경우
    backtrackig(idx + works[idx][0], cost + works[idx][1])

def solution(n, works) :
    global ans
    # 2. 백트래킹 실행
    backtrackig(0, 0)
    # 3. 결과 출력
    print(ans)

if __name__ == '__main__' :
    n = int(input())
    works = [list(map(int, input().split())) for _ in range(n)]
    solution(n, works)