요리 강좌 - KOI 2017 고등부 #3

문제 링크 : http://boj.kr/14869

---

This section is intentionally left blank.

---

Tag : Dynamic Programming, Sliding window, Deque, Pigeon hole principle(...)

\(dp(i,j)\) : 학원 \(i\)에서 \(j\)번째 강좌를 들었을 때의 최소 비용. 즉 우리가 구하고자 하는 답.

\(S(i,j)\) : 학원 \(i\)에서 강좌를 \(1\)부터 \(j\)까지 다 들을 때 드는 비용의 총합. 즉, 비용 배열의 부분합.

\(B_i\) : 학원 \(i\)의 불허용 학원.

다음과 같은 dp 식이 성립한다. (엄밀히는 예외가 좀 있지만 뒤에서 처리하자)

$$ dp(i,j) = \min_{\begin{cases} k\neq i, B_i \\ j-e \le h \le j-s \end{cases}} \{dp(k,h) - S(i,h) + S(i,j) + T\} $$

이 중에서 \(S(i,j)+T\)는 \(k,h\)에 무관하니 빼고, 결국 우리가 관심있는 양은 이놈이다.

$$ \min_{j-e \le h \le j-s}{ \left[\min_{k\neq i, B_i} \{dp(k,h)\} - S(i,h) \right]} \cdots (1)$$

이 양은 결국 \(h\) 에만 의존하니까 어떻게 구해볼 수 있을 것 같다. \(e(i,h)\)를 \((1)\)이라고 정의하자.

\(\min (e(i,h))\)는 구간 \([i-e,i-s]\)에 대한 일종의 구간 최솟값 쿼리인데, 

dp값을 구하는 과정에서 구간이 항상 오른쪽으로 옮겨오므로 deque를 이용해서 이를 sliding window와 같이 관리해줄 수 있다. 

아무리 노력해도 설명이 깔끔하지 되지는 않아서 여기서는 스킵. 개인적으로 질문하시면 답변해 드리겠습니다.

heap을 이용할 경우 전체 복잡도는 \(O(NMlgM)\)이 되는데, fastio를 쓰면 AC가 난다고 한다(...)

Step 1. \(dp(i,j)\) 구하기

$$ dp(i,j) = \begin{cases} \min \{S(i,j), \ \min (e(i,h)) + T + S(i,j)\} & (j \le e) \\ \min (e(i,h)+S(i,j)+T) & (j > e) \end{cases} $$

구현은 각자 편한 대로. 참고로 각 dp값은 \(2.1 \times 10^8\)이니 \(\infty\) 를 여유롭게 \(10^9\) 정도로 잡아도 된다.

Step 2. \(e(i,j)\) 구하기

\(e(i,j)\)는 결국 (\(dp(*,j)\)의 최솟값) \( - \ S(i,j)\)인데, \(*\)에 들어가면 안되는 것이 딱 2개 있다. (자신, 그리고 \(B_i\))

그래서 세번째로 작은 값까지 구해주면 그 3개 중에는 반드시 조건을 만족하는 놈이 있다. 이 아이디어는 BOJ 2969 메뚜기 를 풀 때도 써먹은 적이 있다.

Exception? 마지막 강좌를 듣는 학원

마지막 강좌를 듣는 학원에서는 \(s-1\)개 이하의 강의를 들어도 된다. 

아마 수강이 불가능해지는 경우를 넣지 않기 위해 들어간 조항인 것 같은데, 은근히 성가시다는 사람이 많았다.

나는 맨 뒤에 \(s-1\)개의 비용 \(0\)인 학원을 추가해서 \(dp(1,m) \sim dp(n, m+s-1)\) 중에 최솟값을 구하는 방법으로 해결했다.

---

Complexity : \(O(NM)\)