https://www.acmicpc.net/problem/1006
[1. 문제 분석]
구역의 갯수는 최대 2만개가 존재한다. 2초내에 풀기위해선 효율적인 최적화의 DP가 필요한 문제다. 어떤 구역끼리 병합할지를 결정하면 된다.
[2. 사고 표현하기]
점화식을 세워보자
만약 구역이 1열의 나란한 수열일 경우 점화식은 다음과 같이 세울 수 있다.
- 만약 현재지점과 다음지점을 동시에 처리할 수 있을경우: cache[i]=1+cache[i+2]
- 현재지점만 처리할 수 있을경우: cache[i]=1+cache[i+1]
그렇다면 문제와 같이 2열의 나란한 수열일 경우 어떻게 그리디하게 접근을 해야하나?
1열일 때와 비교하면 다음과 같이 밑의 지점 및 밑에서 일어나는 과정에 대해 살펴보아야한다.
위 그림과 같이 cache[1]는 array[1][1], array[1][2], array[2][1], array[2][2]까지의 병합과정을 처리하는 점화식을 세운다면 큰문제가 생길 수 있다. [1][1]과 [2][1]이 병합을 하고 [2][2]와 [3][2]가 병합을 해야하는 상황이라면 점화식에 모순이 발생하기 떄문이다.
위 그림과 같이 복잡한 상황들에 대해 처리할려면 어떻게 해야할까? 위그림의 색칠된 부분들은 서로 병합 할 수 있는 것이다. 이것들에 대해 일렬로 만들면 계산하기 편할것같다. cache[i]= min(오른쪽 병합+cache[i+2],밑 병합+cache[i+1])인 것이다. 이때 이미 병합한부분에 관해서 접근 할 수 없도록 중복 체크 할 수 없도록 방문체크를 해야한다. 위의그림을 예로들면 i(1<=i<=10)일때는 다음과 같다.
- cache[1]일경우 오른쪽 병합이 가능하다.
=> cache[1]=1+cache[3]이다.- cache[3]의 경우에는 병합가능한것이 없다.
=> cache[3]=1+cache[4]이다.- cache[4]의 경우에는 오른쪽 밑 두개다 병합 가능하다.
=> cache[4]=min(밑병합+cache[5],오른쪽병합+cache[6])이다.- cache[5]의 경우에는 밑과 병합 가능하다.
=> cache[5]=밑병합+cache[6]이다.
....
다음과 같이 진행되며 이미 병합한지점에 관해서는 방문체크후 다시 방문하지 못하도록 한다.
그렇다면 배열이 링버퍼인데 이는 어떻게 처리할 수 있을까?
첫번째 배열은 순서대로 1~16까지 순서대로 넣으면 된다.
[1~16]
두번째 배열은 1을 8뒤에 9를 16뒤에 넣으면 된다.
[2,3,4,5,6,7,8,1,10,11,12,13,14,15,16,9]
이 두배열에 관해서 탐색해서 최솟값 출력하면 된다.
