기상 예측 (BOI 2008)

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

Naive하게 하면 (n-1)Cr * (m-1)Cs 정도의 시간에 풀 수 있으며 당연히 TLE가 난다. ( 상한이 O(2^(n+m) 이다.)

그럼에도 n과 m이 작은 편이라 지수를 하나 정도만 날려도 될 거 같은 범위이다.. 실제로 그렇고.

일단 한가지 축으로 배열을 미리 잘라놓고 생각을 하면, 이는 여러개의 1차원 배열을 자르는 문제로 환원이 된다. 배열은 (s+1)개 나올 것이며, 이를 구간 [1,a1] , [a1+1,a2] ... [as+1,n] 으로 자르는 것이라고 생각하면,

Max(1 <= Array <= s+1)(Max(Sum(Array[i]))) 의 값을 최소화하는 문제가 된다는 것을 알 수 있다.

이는 Parametric Search와 Dynamic Programming 풀이가 존재하는데, 전자는 시간 복잡도가 O(NMlgT) 이고 후자는 O(NM^2 M^3) 의 시간 복잡도를 가진다. 일반적인 상황에서는 전자가 훨씬 낫지만, lgT가 30 가량이라 이번에는 Dynamic Programming이 낫다. 시간 복잡도는 O(2^N * (N+M) * M^2) 이다.

이 시간만 보면 TLE라고 생각할 수 있지만, 실제로는 2^N 이 아니라 (n-1)Cr이라는 점을 감안해보자. 17C9는 24000 정도 이기 때문에 2초 안에 충분히 들어갈법한 풀이이다.

예제 소스를 올렸을 때 유감스럽게도 내 소스를 그대로 베껴 BOJ에 제출하는 사람들이 있었다 ㅡㅡ;; 때문에 소스 올리는 걸 상당히 꺼렸는데, 이번엔 설명이 너무 개판이라 소스를 담아둔다. 본인을 위해서라도 자제하자.

cpp : https://gist.github.com/koosaga/3c004e9cf2e47403ea57