[diamond1][해설미확인,분류확인] boj2586 소방차 (아이디어만)

아이디어만 생각해두고 언젠가 풀려고 했는데 백준이 서비스 종료한다고 해서 아이디어만이라도 적어두려고 한다.. 구현하고 수많은 디버깅을 뚫기에는 이제 알고리즘 문제 풀 시간이 없을 것 같다...

이 문제를 풀 때 수많은 아이디어가 떠올랐던 것 같지만 현재 가장 유력한 아이디어는 다음과 같다.

우선 위와 같이 소방차를 1번부터 맨왼쪽 호스로 차례로 연결한다.  그럼 모든 소방차는 왼쪽 호스로 쏠린 상태일 것이다.

그러나 그런 상태는 절대로 정답이 아닐 것이다. 

그렇다면 위와같은 상태에서 소방차와 호스사이에 칸을 띄워야 할 것이다.  예를들어 소방차 2번부터 한칸을 띄우면 아래와 같이 된다.

위와 같은 상태를 편의상 아래와 같이 나타낸다 치자.

즉 1번소방차, 2번소방차 사이의  1의 의미는 1번과 2번사이에 1칸을 띄웠다는 것이다.  

 

위와 같은 경우는 아래와 같이 될 것이다.

 

그럼 이제 다시 처음으로 돌아와서,  아래와 같은 경우는 어떻게 띄워야 할까?

한 번 계산에 한칸씩 띄운다고 가정했을 때, 한칸 띄웠을 때 가장 소방차와 호스간의 간격의 합이 크게 줄어드는 부분을 띄우면 된다.  그 이유를 알아보자. 위와 같은 상황에서, 4~5번 사이를 띄운다고 치자. 그럼 아래와 같이 된다.  일단 아래는 간격총합이 줄어들긴 한다. (소방차5번, 호스7 번이 최적의 짝인데, 7번에 가까워졌기 때문)

3~4번 사이를 띄우면 아래와 같이 된다. 이때는 소방차4, 소방차5 의 호스의 간격총합이 줄어든다.  

 

반면 0~1번, (소방차1번의 왼쪽)을 띄우면 아래와 같이 된다.이 때 소방차1번의 최적 호스는 1번이였는데 2번으로 갔으므로 간격총합은 증가한다.

 

위와 같은 예시를 살펴보면 , 소방차 사이 간격 어디를 띄우냐에 따라 총합이 증가할 수도, 감소할 수도 있다는 것을 알 수 있다. 그렇다면 왜 가장 총합이 가장 크게 감소하는 부분을 띄우면 될까?   직관적으로 보면 당연히 그리디 하게 띄우는게 타당해 보이지만, 의심할 만한 포인트가 있다.

 어느 간격을 띄우냐에 따른 간격총합 변화량이 아래와 같다고 생각해보자.

우선 4~5번, 3~4번까지는 간격총합이 점차 감소한다.  그러나, 2~3번 사이에선 다시 증가한다. 즉 3번 소방차의 호스간격이 증가한 것이다. 다시 1~2번 사이를 띄우면 크게 총합이 감소한다. 즉 2번 소방차의 간격이 크게 감소한 것이다.  0~1번 사이를 띄우면 다시 증가하므로, 1번 소방차의  간격이 증가한 것이다.

   그럼 이제 직관적으로 3~4번을 띄울지, 1~2번을 띄울지 고민이 될 것이다. 3~4번을 띄우는 이유는 3,4,5번소방차를 띄우는 과정에서 어떤 소방차의 호스 간격도 증가하지 않기 때문이고, 1~2번을 띄우는 이유는 간격총합이 가장 크게 감소하기 때문이다.

즉 1~2번 을 띄우는데 주저하게 되는 이유는 바로 3번 소방차의 간격이 증가하기 때문이다. 그러나 걱정하지 않아도 된다. 

1~2번을 띄우면 2,3,4,5번 소방차가, 3~4번을 띄우면 4,5번 소방차가 띄워지게 된다.    즉 4,5번 소방차는 공통으로 띄워진다. 그럼 차이는 2,3번 소방차가 띄워지냐 마냐인데, 만약 3번소방차 간격이 증가하는게 무서워 띄우지 않게 된다면, 2번소방차는 평생 못띄우게 된다.  1~2번을 띄우고 3번은 이제 더이상 안건들이면 되므로,  특정 소방차의 간격이 증가하는 것은 무시하고 전체 간격총합이 가장 크게 감소하는 사이를 띄우면 된다.

 

 

 

또한 한가지 매우 중요한 점은 간격총합이 가장 크게 줄어드는 소방차 사이를 띄웠으면 이제 더이상은 그 지점보다 왼쪽의 구간은 띄워선 안된다는 것이다.  위에서는 1~2번 사이의 간격이 가장 크게 줄었다.  그래서 1~2번을 띄웠다고 치자. 그 다음 띄울때 만약 1~2번 보다 왼쪽의 지점을 띄우게 된다면, 간격은 늘어나게 될 것이다. 

 

만약 위와 같은 상황이고 3~4번을 띄우는게 최적이라고 치자. 그럼 여기서 2번 3번의 호스를 오른쪽으로 옮기면 간격총합이 증가한다는 것을 알 수 있다.  따라서 다음 번 띄울 때는 3~4번 보다 왼쪽의 지점 ( 0~1 OR 1~2 OR 2~3) 을 띄우면 안된다. 

 

그럼 이제 우리는 소방차를 가장 왼쪽의 호스로 몰아 연결한 뒤, 어느 지점을 띄워야 할지 찾은 뒤 , 다음 번에는 그 지점보다 오른쪽부터 어디를 띄울지 탐색하면 된다.  그러나 이 경우는 최악의 경우  N + N - 1 + N - 2 + ... 1 이 되므로  O(N^2) 이 된다. 

그럼 어떠헥 이 문제를 해결할 수 있을 까? 아래와 같은 경우가 있다고 치자. 

 

이 경우 간격총합이 감소하는 구간과 증가하는 구간이 있다. 이 구간을 따로 저장한다.   

위와 같은 경우     1~3 구간,  5 ~8 구간,  11 ~13 구간 이 감소하는 구간, 나머지 구간은 증가하는 구간이다.

우리는 여기서 감소하는 구간의 가장 오른쪽 구간만 띄워보면 된다는 것을 알 수 있다.    1~3구간에서는  3번지점이 , 5~8 에서는 8번 지점이 가장 간격총합이 크게 감소하기 때문이다.     

  우리가 원래 지점 별로 간격총합을 검사할 때는 22번을 검사 (모든 점의 갯수) 해야 하지만,  이렇게 감소하는 구간의 가장 오른쪽만 조사한다면 3번만 검사하면 된다. 

  한 간격을 띄울 때 간격 총합의 변화량은 어떻게 계산할까? 다음과 같이 한칸씩 오른쪽으로 띄울 때, 현재 전체 총합에서 가장 호스의 왼쪽, (b1) 과 오른쪽 (b4)만 고려하면 되므로, 변화량 계산의 시간복잡도는 O(1)이 될 것이다.

 

자, 그러나 여전히 감소 구간의 오른쪽을 검사해도, 최악의 경우에는 한번 검사할 때마다 O(N)번씩 검사해야 할 수도 있다,.

그러나 그렇지 않다.

위의 그림은 소방차와 연결된 호스를 한칸 오른쪽으로 옮길 때 의 양상을 나타낸 것이다. 

우부터 좌로 훑어보면 맨오른쪽 소방차는 호스를 오른쪽으로 이동하면 간격 총합이 증가한다. (증가구간)

두번째 소방차는 호스를 이동하면 감소구간에서 증가구간으로 스위칭 하는 과정이므로, 간격총합이 증가할지 감소할지 모른다. 계산해봐야 한다. 

3~4번째 소방차는 오른쪽으로 이동시 확실히 간격총합이 감소한다. 

여기서 아까 설명했듯이 간격총합을 최소로 하는 포인트를 찾을 때는 감소구간들에서 맨 왼쪽만 고려하면 된다.

또한 여기서 시간복잡도를 O(N^2)이 아니라는 것을 증명하기 위해 매우 중요한 포인트는, 감소구간의 맨 오른쪽 부분이 다음 간격시에는 무조건 스위칭 구간이 된다는 것이다.

위와 같이 왼쪽은 한칸 띄우기 전이고, 한칸 띄운뒤는 오른쪽과 같이 된다. 여기서 감소구간의 맨오른쪽은 스위칭 구간이 된것을 알 수 있다. 이유는 단순하다. 띄우기 전 구간에서 3번째 소방차가 3번째호스에서 스위칭 구간이였는데, 그 소방차보다 왼쪽에 있는 2번소방차가  띄운 후 3번 호스와 매칭되면서 반드시 스위칭 구간이 된다. 핵심은 감소구간의 오른쪽 구간은 스위칭 구간이고, 감소구간의 맨 오른쪽 지점은 현재 스위칭 지점보다 왼쪽에 있기 때문에 반드시 다음에 스위칭 구간이 된다.

 그럼 다음과 같은 사실을 알 수 있다. 

 

 

1. 한칸을 띄울때의 간격총합이 최소로 감소하는 지점은 각 감소구간의 맨왼쪽 지점으로 좁혀진다.

2.감소구간의 맨 오른쪽 지점은 다음 번에 반드시 스위칭 구간이 된다.

 

 

만약 N이 10만 개고, 감소구간이 100개, 각각의 감소구간은 1000개의 소방차로 이루어져있다고 생각하자.

각 시행에서 어디를 띄울지는 각 감소구간의 맨 왼쪽, 즉 100개만 고려하면 된다. 그리고 그 시행이 끝날 때마다, 각 감소구간의 맨오른쪽은 무조건 스위칭 구간이 된다. 즉 , 각 감소구간의 소방차수가 한개씩 감소한다. 즉 500번 시행 한다면, 각 감소구간은 500개의 소방차로 이루어져있을 것이다. 1000번 시행시는 감소구간이 없어져 있을 것이다.

즉 위의 두가지 특성으로, O(N)으로 구할 수 있다.

각 시행시 어디를 띄울지 특정한다면, 이제 그 지점의 왼쪽은 더이상 고려하지 않아도 되므로, 그 지점~ 맨오른쪽의 지점들만 고려하면 된다.

 또한 유의할 점은, 스위칭 구간은 감소구간의 맨오른쪽뿐만 아니라, 감소구간의 중간에서도 불쑥 나타날 수 있다.

몇번 띄웠을 때 각각의 소방차에서 스위칭 구간이 나타나는지는, 투포인터(혹은 슬라이딩 윈도우?)로 알 수 있다.

투포인터로 n번째 소방차가 m번째 호스와 매칭시 스위칭 구간임을 알아내면, n + 1번 소방차는 최소 m번째 이상의 호스와 매칭시 스위칭 구간이므로 m번째부터 고려한다.    또한 n번째 소방차가 m번째 호스와 매칭시  m-n만큼 간격을 띄웠을 때 매칭됨을 유의한다.

 

요약:

 

1. 각 소방차의 사이 지점을 탐색, 그 지점들을 집합으로 하는 감소구간, 증가구간, 스위칭구간(집합갯수 1개) 를 구분한다.

2. 각 소방차마다 몇칸을 띄웠을 때(호스를 오른쪽으로 몇칸 이동했을 때) 스위칭 구간이 되는지 알아낸다. O(N)

3.각 감소구간의 맨 왼쪽을 띄워보면서, 어느 지점을 뜨웟을 때 간격총합이 가장 크게 감소하는지 찾는다. 이제 다음 띄울 때는 그 지점부터 고려한다.(그 지점의 왼쪽부분은 더이상 고려대상 X) . 그 후 감소한 간격총합을 토대로 정답을 업데이트

4. 이제 그 지점을 띄웠을 때, 그 지점부터 맨 오른쪽 까지 구간중 어느 지점이 스위칭 구간이 되는지는 2번에서 알아냈으므로, 그걸 토대로 감소구간을 새로 업데이트. (이때 최소 감소구간 갯수 이상의 소방차가 감소구간에서 스위칭 구간으로 전환)

5.2~4번 구간을 반복한다. 만약어떤 지점에서도 간격총합이 감소하지 않을 경우, 사이클을 멈춘다.