다이나믹 -- 시작복잡도 줄이기

dynamic programming 문제들중 

와 같은 점화식을 가진 문제들에 대해 생각해보자.

실제로 최근 KOI에서도 위와 같은 점화식을 가진 문제가 몇몇 나왔는데

2011 전국 중등부3 번이라던가

2011 지역 고등부5 번을 예로 들 수 있다.

위와 같은 점화식을 가진 문제는 특수한 경우에 따라 시간복잡도를 

에서 으로 바꿔 풀 수 있다.

1. commando (APIO 2010)

위 문제의 점화식을 나타내보면

여기서 bX항은 그룹을 어떻게 나누는지에는 상관없이 항상 그 값은  과 같게 된다.

따라서 위 점화식을

 로 두고 마지막에 b*(x1+x2..+xn) 을 더해주면 위와같은 점화식이 된다는것을 확인할 수 있다. 그리고 c는 j값에 상관없이 항상 일정한 값을 가지기 때문에

우리는 고정된 i 에 대하여 

 의 값을만에 구할수 있다면 시간복잡도는 이 될것이다.

편의상

 로 정의하면,  점화식을 다음과 같이 나타낼수 있다.

두번째 식에서 세번째 식으로 넘어가는 과정에서 항이 밖으로 빠저나간 이유는 D(i)값을 구할때 고정된 i에 대해서 생각하기 때문이다.  위와 같이 정의한후  라는 함수를 생각해 보자.

그러면 위 함수는 일정한 특징을 가진 일차함수가 된다.

<특징1>  j가 증가함에 따라서 기울기가 증가하는 함수이다. (-5 <= a <=-1 임으로)

<특징2>  기울기가 동일한 j와 j'는 존재하지 않는다.

이러한 사실을 알았을때, i = 5 일때 임의의 그래프를 그려보면

다음과 같습니다. 이러한 후보들 중에서 값이 주어졌을때 함수값이 최대가 되는 j후보를 찾는것이 문제의 핵심인데,

그러면 모든 j의 후보에 대해서 교점을 찾아서 함숫값을 구하면 각 i에 대해서 N번 즉 O(N^2) 이 되어버린다.

그러나 아까 찾은 특징을 생각해 보면 어떤 j에 대하여 그 함수값이 최대가 되는 어떠한 구간들을 각각 가지고 있다.

그렇다면 j후보에 대해서 직선들의 교점에 대한 list들을 관리해 주면서, 값이 주어졌을때 최댓값으로 인정받는 j를 binary search 로 찾아주고, i -> i+1이 될때 i에 대한 직선을 list에 update 시켜 준다면 풀이는 완성이 되었다.

직선을 update시켜줄때 주의해야할 점이 하나 있는데, 

다음과 같은 상황일때이다. 이런 상황에선 list들을 뒤에서 부터 pop해주면서 필요없는 직선은 버리면 된다.

에서 으로 줄이는 아이디어는 간단하다.

바로 값은 항상 증가한다는 사실이다. 즉 binary search로 j후보를 찾을 필요없이 list의 앞에서 부터 값이 최댓값으로 인정받는 구간이 아니라면 pop해버리면 된다. 아까 말했듣이 값은 항상 증가하기때문에 pop한 j의 후보에 대해선 다시 참조할 일이 없기 때문이다.

2. 책장 (KOI 2011)

// 작성중