동일한 크기의 목록이 두 개 있다고 가정합니다. 이 목록은 마감일과 학점이며 코스 할당을 나타냅니다. 여기서 Deadline[i]은 과제 i의 마감일을 나타내고 credits[i]는 과제 i에 대해 받는 학점의 양을 나타냅니다. 과제를 완료하는 데 하루가 있으며 마감일 이전이나 당일에 완료할 수 있습니다. 동시에 여러 과제를 수행할 수 없습니다. 일부 과제를 완료하여 얻을 수 있는 최대 크레딧을 찾아야 합니다.
따라서 입력이 마감일 =[1, 2, 2, 2] 크레딧 =[4, 5, 6, 7]과 같으면 출력은 18이 됩니다. 0일에 크레딧 5로 할당을 완료할 수 있기 때문입니다. 1일차에 6학점으로 과제를 3일차에 7학점으로 과제를 완료합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- a :=한 쌍의 마감일과 크레딧을 만들고 크레딧을 기준으로 내림차순으로 정렬합니다.
- 비어 있으면
- 0을 반환
- res :=크기 목록(1 + 최대 기한) 및 0으로 채우기
- ans :=0
- 각 쌍(i, j)에 대해 do
- i 범위에서 0까지의 k에 대해 1만큼 감소, do
- res[k]가 0이면
- res[k] :=1
- ans :=ans + j
- 루프에서 나오다
- res[k]가 0이면
- i 범위에서 0까지의 k에 대해 1만큼 감소, do
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, deadlines, credits): a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True) if not a: return 0 res = [0] * (max(deadlines) + 1) ans = 0 for i, j in a: for k in range(i, -1, -1): if not res[k]: res[k] = 1 ans += j break return ans ob = Solution() deadlines = [1, 2, 2, 2] credits = [4, 5, 6, 7] print(ob.solve(deadlines, credits))
입력
[1, 2, 2, 2], [4, 5, 6, 7]
출력
18