1. 문제 소개

2054. Two Best Non-Overlapping Events

2. 나의 풀이

내 힘으로는 풀지 못했다.

3. 다른 풀이

Editorial의 풀이는 다음과 같다.
dp와 binary search를 사용한 풀이였다.
시간복잡도는 $O(N log N)$이다.

class Solution:
    def maxTwoEvents(self, events):
        events.sort()                                      # (start, end, value) 기준으로 기본 정렬: start 우선, 동률이면 end/value 순
        dp = [[-1] * 3 for _ in range(len(events))]        # dp[idx][cnt]: idx부터 탐색, 이미 cnt개 선택했을 때의 최대 합(메모이제이션)
        return self.find_events(events, 0, 0, dp)          # 0번 인덱스부터, 0개 선택 상태로 시작

    def find_events(self, events, idx, cnt, dp):
        if cnt == 2 or idx >= len(events):                 # 2개를 이미 골랐거나, 끝까지 탐색했으면 더 이상 얻을 가치 없음
            return 0

        if dp[idx][cnt] == -1:                             # 아직 계산하지 않은 상태라면 계산 수행
            end = events[idx][1]                           # 현재 이벤트의 종료 시간
            lo, hi = idx + 1, len(events) - 1              # 다음 후보 범위: idx+1 ~ 마지막

            # 이진 탐색: start > end인 "다음 이벤트"의 시작 인덱스 후보를 찾으려는 의도
            # - 목표는 lower_bound(start > end)에 해당하는 위치를 찾는 것
            while lo < hi:
                mid = lo + ((hi - lo) >> 1)                # 중간 인덱스(오른쪽 편향 아님)
                if events[mid][0] > end:                   # mid의 시작이 end보다 크면, 더 왼쪽에도 조건 만족이 있을 수 있어 hi를 줄임
                    hi = mid
                else:                                      # start <= end면 겹치므로, 더 오른쪽으로 이동
                    lo = mid + 1

            # include: 현재 idx 이벤트를 선택하는 경우의 가치
            # - 다음으로는 (겹치지 않는) start > end인 이벤트부터 재귀 탐색
            # - 조건을 만족하지 못하면(또는 범위를 벗어나면) 추가 이득은 0
            include = events[idx][2] + (
                self.find_events(events, lo, cnt + 1, dp)
                if lo < len(events) and events[lo][0] > end
                else 0
            )

            # exclude: 현재 idx 이벤트를 건너뛰고 다음 idx+1로 진행
            exclude = self.find_events(events, idx + 1, cnt, dp)

            dp[idx][cnt] = max(include, exclude)           # 선택/비선택 중 최댓값 저장

        return dp[idx][cnt]                                # 메모된 결과 반환

4. 마무리

dp를 다시 공부해야겠다.