[파이썬/python] 백준 - 17099 Contest

문제

https://www.acmicpc.net/problem/17099

---

문제 설명

1. 총 N개의 대회가 입력으로 주어진다.(시작시간, 종료시간, 상금)
   1. 대회를 치를 수 있는 개수에는 제한이 없다.
   2. 대회가 끝나는 시간과 다음 대회가 시작하는 시간이 같으면 안 된다.
2. 최대로 상금을 벌 수 있는 방법으로 대회를 치렀을 때 최대 상금을 출력한다. 

---

풀이

문제를 보면 회의 문제랑 유사하다는 것을 느낄 수 있었다.

그래서 우선적으로 생각한 알고리즘은 그리디와 DP정도였다.

 

문제의 조건 중 "전 대회가 끝나는 시간과 다음 대회가 시작하는 시간이 같으면 안 된다" 조건이 기존 회의 문제들과의 차이점이었다.

또한 구하고자 하는 것이 최대 상금이라는 것? 정도

 

일단 최댓값을 구하는 것이기 때문에 누적 상금을 구하면서 DP로 푸는 것이 더 옳은 방향성이라고 판단했다.

 

최초 접근은 단순하게 2차원 DP를 통해서 모든 시간을 갱신하는 방식이었다. 당연하게도 $N$이 $3*10^5$였기 때문에 $N^2$으로 문제를 풀이하기는 어려움이 존재했다.

 

그렇다면 이 문제는 $N^2$보다 낮은 시간복잡도로 문제를 풀어야 하는데, 1차원 DP로 풀기에는 내 앞에 값을 무엇을 선택해야 하는가? 에 대한 고민이 있었다.

 

예를 들면 이런 것이다.

현재 대회가 (6,27,7) 일 때 내 앞에 존재하는 무수한 값들 중 어떤 것을 선택하는 것이 최적이냐는 것이다.

 

일단 점화식을 먼저 세워봤다.

누적된 최댓값을 구하는 것이기 때문에 dp [i] = (value [i] + dp [j], dp [i-1]) 정도로 세울 수 있었다.

여기서 j가 의미하는 바는 "현재 대회를 이어서 진행할 수 있는 이전 dp값 중 최대인 값의 인덱스"이다.

 

그렇다면 이 문제의 핵심은 어떻게 j를 구할 것인가?로 고민의 범위를 줄일 수 있다.

 

j는 현재 내 대회의 시작시간보다 빠른 이전 대회들 중에 탐색을 진행해야 하기 때문에 회의 종료시간만 따로 모아둔 배열 end를 만들었다.

 

0번째 대회부터 현재 대회의 인덱스 i 이전까지 탐색하여 그중 최적의 선택을 해야 한다.

하지만 그 앞의 대회의 수는 매번 탐색을 진행하면 $1 + 2 + 3 + 4.... 3*10^5$의 시간복잡도가 소요되므로 결국엔 시간초과가 발생한다.

 

그렇기에 순서가 존재할 때 $logN$으로 원하는 값을 찾아낼 수 있는 이분탐색!! 을 떠올렸다.

 

사실 정말 오래 걸렸다. 그 앞에 있는 대회 중에 내가 선택할 수 있는 대회를 어떻게 가려낼지를 정말 오래 고민했다.. 힙구조도 고민해 보고.. 뭐 등등

 

그래서 매 대회의 값을 경신하면서 end배열에서 현재 대회의 시작시간보다 더 작은 대회를 찾았다.

여기서 중요한 포인트가 하나 있다.

 

end = [1,2,2,5,6,9,13]이라는 배열이 존재할 때 현재 회의의 시작시간이 4라고 가정하자.

그렇다면 우리는 4보다 작은 회의를 찾아야 하는데 그중에 가장 오른쪽에 있는 값을 찾아야 한다.

 

왜냐하면 결국 dp로 순차적으로 누적된 최댓값을 갱신하기 때문이다.

중복된 값이 있더라도 결국에는 가장 오른쪽에 있는 값이 최댓값이기 때문에 이를 탐색했다.

 

이 문제는 이분탐색 + DP를 통해서 정답을 도출할 수 있었다.

 

그런데 문제를 풀고 알고리즘 분류를 봤는데 이분탐색이 없었다. 그래서 다른 사람 코드를 봤는데 다들 이분탐색을 썼던데

문제 출제자의 의도가 이런 게 아닌가? 생각했다. 애초에 제출도 400개도 안 되는 문제여서 그럴 수 있나..? 싶기도 하고...

---

코드

import sys
input = sys.stdin.readline

n = int(input())

arr = [[0,0,0]]

for i in range(n):
    arr.append(list(map(int,input().split())))
arr.sort(key = lambda x: (x[1]))

end = [arr[i][1] for i in range(n+1)]

dp = [0 for _ in range(n+1)]
def binary_search(idx, target):
    s = 0
    e = idx
    
    while s+1 < e:
        mid = (s + e) // 2
        
        if end[mid] < target:
            s = mid
        else:
            e = mid
    return s

for i in range(1, n+1):
    j  = binary_search(i, arr[i][0])
    dp[i] = max(arr[i][2] + dp[j], dp[i-1])

print(dp[-1])

---

시간복잡도

• DP를 갱신할 때 $O(N)$, 이분탐색을 진행할 때 $O(logN)$ (실제로는 $log1 + log2... logN$정도이다.)이므로
  $O(NlogN)$정도의 시간복잡도가 소요된다.
• N은 최악의 경우 $3*10^5$이므로 $O(10^6)$정도의 시간복잡도를 예상해 볼 수 있겠다.