[CodeTree/Python] 최대 이익 구하기 2

문제

최대 이익 구하기 2

n일 동안 하루에 하나씩 일을 지급받습니다. 일은 하는데 걸리는 날짜 수 Ti​와, 받는 보수 Pi​가 정해져 있습니다.

여러 개의 일은 동시에 할 수 없고, 모든 일은 n일 안에 마무리되어야 합니다.

예를 들어서, n=5 일 때 다음의 상황을 생각해봅시다.

이런 경우, 1일에 일을 하게 되면 1일~3일에 걸쳐서 일하게 되며, 100의 보수를 지급받습니다. 그렇기 때문에, 1일에 일하기로 하면 2일 또는 3일에 할당된 일은 할 수 없습니다.

또, 4일에는 일을 할 수 없는데, 이는 4일에 시작한 일은 n일 안에 마무리되지 않기 때문입니다.

따라서 위의 예시에서 가장 많은 이익을 얻기 위해서는, 1일과 5일에 할당된 일을 해서 120의 이익을 얻어야 합니다.

지급받은 일을 하는데 걸리는 날짜 수와 일을 완수하면 받는 보수가 주어질 때, n일 동안 가장 많이 얻을 수 있는 이익은 얼마인지 구하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에 n이 주어집니다.

두 번째 줄부터 n개의 줄에 걸쳐 일하는데 걸리는 날짜 수 Ti​와 보수 Pi​가 공백을 사이에 두고 한 줄에 하나씩 주어집니다.

• 1 ≤ n ≤ 15
• 1 ≤ Ti​ ≤ 5
• 1 ≤ Pi​ ≤ 1,000

출력 형식

주어진 날짜 안에 얻을 수 있는 최대 이익을 출력합니다.

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

 

풀이

n = int(input())
li = []
for i in range(n):
    t, p = map(int, input().split())
    li.append((t, p))

def max_p(n, li):
    memo = [-1] * n # 메모제이션 리스트 초기화
    
    def count(day):
        if day >= n:
            return 0 # n 이상이면 일을 시작할 수 없으므로 보수 0
        
        if memo[day] != -1:
            return memo[day] # 메모제이션 되어 있으면 값 반환
        
        # 일 넘기는 날
        max_p_skip = count(day + 1)
        # 보수 저장하지 않고 다음날 탐색(재귀 호출)해서 일 안했을 때 최대 이익 계산
        
        # 새 일 시작하는 날
        max_p_work = 0
        if day + li[day][0] <= n:  # 일을 마칠 수 있는 경우에만 새 일 진행
            max_p_work = li[day][1] + count(day + li[day][0])
            # 현재 일의 보수 저장하고 날짜 추가한 후 새 일 진행 경우의 수 탐색(재귀 호출)
        
        memo[day] = max(max_p_skip, max_p_work)
        # 해당 일자 기준으로 일을 했을 때 혹은 하지 않았을 때에 대한 최대 이익 저장
        return memo[day]
    
    return count(0) # 초기 일자 지정


# 결과 출력
print(max_p(n, li))

1. 조건 확인
   • 여러 일은 동시에 할 수 없다.
   • 태스크는 매일 하나씩 주어진다.
   • 모든 일은 n일 안에 마무리되어야 한다.
2. 함수 정의
   • n = 총 주어진 날짜(아래 줄마다 주어지는 태스크가 순서대로 할당됨)
     t, p = 일하는 데 걸리는 날짜, 보수(최대: max_p)
     li = (t, p)의 리스트
   • 일하는 날 / 일 넘기는 날 분리(날마다 하나씩 주어지므로)
   • 메모제이션 활용해보기
     -> 리스트(memo) 초기화: 각 일자별 일 유무에 따른 최대 이익 저장
   • 백트래킹(모든 경우의 수 순회)
3. 풀이
   • 코드 주석 참조