문제 질문 좀


예를 들어서 데이터가 10개(N) 있고 buy & sell 하는 최대횟수가 2번(K)이라고 할게


N = 10 / K = 2

data = 7 41 35 33 39 11 24 13 45 43


문제가 왼쪽에서 오른쪽으로 쭉 이동하면서 K번 buy & sell 할 때의 최대이익 구하기거든 (buy buy sell sell 은 안 됨)

즉, 위 예시의 답은 (41 - 7) + (45 - 11) = 34 + 34 = 68 이야


이 때 O(N) 이나 O(logN) 정도로 어찌 구함?

N <= 30,000 , K <= 6,000 이라서 단순 DP로는 메모리 부족이더라고