문제 정의
길이가 모두 같은 세 개의 리스트가 있다고 가정해 보겠습니다. 바로 마감일(deadlines), 학점(credits), 소요 일수(durations)이며, 각 리스트는 과제 정보를 담고 있습니다.
i번째 과제를 기준으로 각 리스트의 의미는 다음과 같습니다.
deadlines[i]— 해당 과제의 마감일credits[i]— 과제를 완료했을 때 받는 학점durations[i]— 과제를 끝내는 데 필요한 일수
이때 지켜야 할 규칙은 다음과 같습니다.
- 한 과제를 완료하기 전에는 다른 과제를 시작할 수 없습니다.
- 마감일 당일에 과제를 끝내도 인정됩니다.
- 현재 시점은 0일차의 시작입니다.
예를 들어 입력이 아래와 같다면 출력은 10이 됩니다.
deadlines = [7, 5, 10] credits = [8, 7, 10] durations = [5, 4, 10]
해결 전략: 동적 계획법(DP)
이 문제는 각 과제에 대해 "수행한다 vs 건너뛴다"라는 두 가지 선택을 반복적으로 고려해야 하므로, 동적 계획법으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 세 리스트를
zip()으로 묶어 하나의 작업 목록(jobs)으로 만든 뒤 정렬합니다. dp(i, day)함수는 "i번째 과제부터 고려하고, 현재 day일차일 때 얻을 수 있는 최대 학점"을 반환합니다.- 현재 과제를 건너뛰는 경우:
dp(i + 1, day) - 현재 과제를 수행하는 경우: 마감일 안에 끝낼 수 있다면(
day + duration - 1 <= deadline)dp(i + 1, day + duration) + credit - 두 경우 중 더 큰 값을 선택해 반환합니다.
파이썬 구현 코드
class Solution:
def solve(self, deadlines, credits, durations):
jobs = sorted(zip(deadlines, durations, credits))
def dp(i=0, day=0):
# 모든 과제를 확인했다면 0 반환
if i >= len(jobs):
return 0
# 현재 과제를 건너뛰는 경우
ans = dp(i + 1, day)
deadline, duration, credit = jobs[i]
# 마감일 내에 완료 가능하면 수행하는 경우도 고려
if day + duration - 1 <= deadline:
ans = max(ans, dp(i + 1, day + duration) + credit)
return ans
return dp()
ob = Solution()
deadlines = [7, 5, 10]
credits = [8, 7, 10]
durations = [5, 4, 10]
print(ob.solve(deadlines, credits, durations))
입력
[7, 5, 10], [8, 7, 10], [5, 4, 10]
출력
10
코드 동작 원리 살펴보기
위 예제에서 과제는 마감일 순으로 정렬되어 [(5, 4, 7), (7, 5, 8), (10, 10, 10)]이 됩니다. 여기서 흥미로운 점은, 앞의 두 과제를 모두 수행하면 두 번째 과제가 8일차에 끝나 마감일(7일)을 초과하므로 학점 7을 받을 수 없다는 것입니다. 대신 첫 두 과제를 건너뛰고 세 번째 과제만 수행하면 0~9일차에 완료되어 마감일(10일) 안에 들어가므로 학점 10을 온전히 얻게 됩니다. 이것이 출력이 10이 되는 이유입니다.
이처럼 재귀 호출을 통해 모든 조합을 탐색하면서도, 동일한 상태(i, day)에 대한 중복 계산을 피하면 성능을 크게 개선할 수 있습니다. 실무에서는 functools.lru_cache 데코레이터를 dp 함수에 적용해 메모이제이션을 추가하는 것이 좋은 최적화 방법입니다.