Pick One 을 눌러 랜덤 문제를 한 개 추출하였다.
1751. Maximum Number of Events That Can Be Attended II
예제를 먼저 살펴보았다.
k 개의 이벤트를 고를 수 있고, 이벤트는 겹치면 안 되는 모양이다. 이벤트의 cost 가 가장 큰 조합을 찾는 문제인 듯 하다.
DP 문제처럼 생겼다.
시작 날짜로 정렬해준 후 f(i, j) 를 i 번째 이후로 최대 j 개의 이벤트를 골랐을 때 최대값이라 하자.
f(i, j) = max (i 번째 이벤트를 고른 경우), (고르지 않은 경우)
라고 할 수 있다.
func maxValue(_ events: [[Int]], _ k: Int) -> Int {
let events = events.sorted { $0[0] < $1[0] }
let arr = Array(repeating: -1, count: k + 1)
var dp = Array(repeating: arr, count: events.count)
func f(_ i: Int, _ j: Int) -> Int {
if i >= events.count || j < 1 {
return 0
}
if dp[i][j] != -1 {
return dp[i][j]
}
let e = events[i]
// let k = events.firstIndex { $0[0] > e[1] } ?? Int.max
var k = i + 1
while k < events.count, events[i][1] >= events[k][0] {
k += 1
}
dp[i][j] = max( f(i+1, j), f(k, j-1) + e[2] )
return dp[i][j]
}
return f(0, k)
}
메모이제이션이 없거나 firstIndex 를 사용하면 시간 제한에 걸린다...