[diamond5][해설안봄,분류확인] 6171 땅따먹기 (눈물겨운 동고쇼끝에..)

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

 

이 문제를 풀려고 몇일동안 눈물의 동고쇼를 펼쳤다..  분명히 이렇게 하면 풀릴 것같은 각이 보여서 코드를 짜면 사실 잘 못 생각한 거였고,, 이 과정을 수없이 반복하며 너무 힘들었지만 풀고 말았다.. 

 도저히 각이 안나왔으면 진작에 포기했을텐데 풀릴 것같은 희망고문이 사람의 이성을 마비시키는 것 같다,,,

분류를 보고 볼록껍질 최적화? 가 뭘까 하고 검색하고 그림을 보자마자 아, 그리디하게 풀되 좌표를 미리 지정해서 풀면 되겠거니 하는 생각과, 문제에서 어떻게 볼록껍질을 적용해볼지 관찰하는 건 어렵지 않았으나, 볼록껍질이 낯선 나로서는 그 뒤의 과정이 너무나도 힘들었다

  볼록껍질을 어떻게 써볼까 하고 고민하던 중 약간 로그 곡선 느낌이 나는구나 하고, 로그 곡선 느낌이 나게 직사각형을 배치해 보았었다. 

이렇게 그려보고, 기울기가 다른 직선 여러개를 고려하려고 할 때, 지금까지 직사각형 넓이의 최솟값은 상수로,  너비를 기울기로 하면 되겠다는 생각은 그렇게 어렵지 않았다. 

우선 w1,h1 인 1번 직사각형을 선택한다. 

그후, w1를 유지하면서  너비가 w1, 높이가 h2인 직사각형, (간편히 (w1,h2))라 한다) 를 만들던가, 아니면 새로 w2로 업데이트하면서 w2*h2 인 직사각형을 포함할지 정할 수가 있다. 
 여기서  w1를 유지하면 y = w1 * x  (x는 높이, y 는 직사각형의 넓이의 합),  w2로 업데이트 하면  y = w2 * x + w1 * h1 이 될 것이다.  마찬가지로 w3로 업데이트하려고 하면 y = w3 * x  + (지금 까지의 직사각형 넓이합 최솟값) 이 될 것이다.

이 직선들을 한곳에 정리하면 이렇게 될 것이다.

여기서  k2 는 1번 , 2번 직사각형 넓이의 합의 최솟값 이 된다.   즉  w1*h2 혹은 w1*h1 + w2*h2 의 값중 최솟값이 되는 것이다.

마찬가지로 k3는 1~3번까지 직사각형 넓이합의 최솟값이다.

 

이렇게 그래프들을 겹겹히 놓으면 볼록한 곡선 느낌이 나기때문에 볼록껍질이라고 불리는 것 같다 (작명센스가 대단하다)

그럼 저렇게 그래프들을 놓으면 무엇을 관찰 할 수 있을 까? 

중요한 사실은 1번그래프(w1 * x)와 2번그래프 (w2 * x  + k1)에서 2번그래프가 1번그래프를 추월(교점에서 만난 이후)하게 되면 슬프게도(?) 1번 그래프는 영영 기억에서 삭제시켜도 된다. 추월한 이후로는 2번 그래프가 1번 그래프보다 무조건 작기 때문이다. 추월이후로는 2번그래프가 1번그래프보다 작고, w2가 w1보다 작기때문에 무조건이다.

오.. 그럼 1번 그래프를 추월한 2번그래프로 그래프를 업데이트 하고, 2번 그래프로 가다가 3번 그래프로 업데이트 하는식인가...?

당연히 그렇지는 않다..  h가 증가함에 따라 1번 그래프를 유지하는게 2번그래프로 업데이트하는것보다 최솟값이 될 수도 있기 때문이다.

그럼 언제까지 w1를 유지하다가 다른 직선으로 갈아치워야 할까? 

  h1  , h2, h3 ... 증가함에 따라 기울기가 w2, w3, 인 직선을 만들면서  w1 * x 직선과의 교점을 구하고, 그 교점을 넘어서면 그때 바꾸면 될 것이다.

이런식으로 1번 2번 , 1번 3번, 1번 4번 과의 교점을 차례로 구하면서, 1번 을 가장 빨리 추월하는 직선으로 업데이트 하면 된다. (교점이 가장 빠른 직선). 여기서는 2번 선이 될 것이다. 

유의해야 할점은 무조건 직선이 나중으로 갈수록 교점이 나중에 생기리라는 법은 없다는 것이다. 위에서처럼, 1번 4번 교점이 1번 3번 교점보다 먼저 생길 수도 있다는 것이다. 

 그렇다면 가장 빠른 교점을 구하기 위해, 각 점 마다 N개씩 교점을 구해서 최솟값을 구하면  시간복잡도는 O(N^2)이 되는 것인가? 그럼 무조건 시간초과일텐데/? 

이것을 해결하기 위해 우선 다음과 같이 진행하였다.

 

다음에서 h2에서  2번 선을 생성한다. 2번선의 기울기는 w2 이고, y절편(k1값) 은 w1*h1 이다.   여기서 한번 2번선이 생성되면, h3, h4... 등으로 가도 2번선은 h2일때 만들어진 그대로 라는 것을 꼭 잊지 말아야 한다.

 

그리고, 앞으로  1번선 2번선의 교점 i2에서 w2가 w1을 제거하고 업데이트 될 것임을  저장한다.

 

그리고 h3에서는 2번선과 3번선의 교점 i3를 구하고 w3가 w2를 i3에서 제거함을 저장한다.

왜 3번선은 2번선, 2번선은 1번선의 교점만을 저장할까?  교점(1,2)보다 교점(1,3) 이 더 먼저 생길수도 있는데 말이다. 

우선 다음을 꼭 알고 있어야 한다.

 

다음과 같은 경우에 5번선이 가장 먼저  추월하는 선은 4번선이다. 즉 5번선이 가장 먼저 3번선을 추월하는 경우는 없다.

근데 석연치가 않다.

 

다음과 같은 경우에는 5번선이 가장 먼저 만나는 선은 1번선인데 말이다. 

그런데 여기서 2번선을 봐보자. 교점(1,5) 전에 2번선이 1번선과 먼저 만나서, 1번선은 삭제된다.

결국

다음과 같이 2번, 3번, 4번 선들이 나란히 남게 된다.

즉 5번선은 4번선, 3번선, 2번선... 순차적으로 추월할 수 있고 1번선같이 순서를 무시하고 튀어나온 녀석들은 이미 다른 선에 의해 삭제된 잔상이다. (그것은 제 잔상 입니다만)

 

이게 일반화 될 수 있는지 생각해보자.

논리적으로 간단히 생각해봐도 1번선이  2,3,4번선들을 뚫고 가장 먼저 5번선과 만나려면 우선 2번선을 뚫어야 하고, 빨간 색 점에서 교점이 생성되어 삭제 될 것이다.

 

 

 

 

이번엔 다음과 같은 상황을 보자

4번선은 1번선과 가장 먼저 만나지만 1번선은 2번선에 의해 이미 삭제됨. 그다음은 2번선과 만나지만 2번선은 3번선에 의해 이미삭제됨,  결국 4번선은 3번선만 삭제하게 됨.

3번선은 1번선과 가장먼저 만나지만 1번선은 2번선에 의해 삭제됨,  결국 3번선은 2번선만 삭제

2번선은 1번선과 가장먼저 만나고   결국 2번선은 1번선만 삭제

즉 순서는    2번선에 의해 1번선 삭제 -> 2번선에 의해 3번선 삭제, -> 4번선에 의해 3번선 삭제.

 

이렇게 선이 뒤죽박죽 꼬여 있는 것 같아도 결국 순차적으로 삭제되기 때문에 n번째 선은 n - 1번째 선과의 교점만 생각하면 될 것이다.

따라서 다음과 같은 경우에, 2번선와 1번선의 교점을 찾고 i1에서 1번선이 삭제됨을 예고,  

그이후에 순차적으로 3번선,2번선의 교점을 찾고, i2에서 2번선이 삭제됨을 예고... 식으로 해나가면 될 거 같다.

그러나 여기에도 미스가 있다.

 

다음과 같이 1번선이 가장 먼저 3번선과 만나게 될 경우 3번선으로 업데이트를 해야 하는데 우리는 1,2번사이의 교점밖에 만들지 않아 3번선은 언제 만날지 모른다는 것이다. 

그렇다면 어떻게 해아 할까. 우리는 아까 발견한 원칙에 따라 3번선이 가장 먼저 삭제하는 건 2번선이라는 것을 알 수 있다. 그러나 이것은 3번선이 2번선만 삭제 할수 있다는 것은 아니다. 순차적으로 2번,1번... 이런식으로 삭제할 수 있다는 것이다.

다음과 같은 경우에 4번선이 3번선, 2번선, 1번선을 순차적으로 삭제할 수 있음을 확인할 수 있다.

 아래와 같이 만약 선이 뒤죽박죽이 되어 2번, 3번, 1번선을 순으로 만나게 될경우엔 2번선은 이미 3번선에 의해 삭제된 상태일 태고 3번,1번을 순차적으로 삭제할 수 있게 된다.

 

 

 

 

 

 

 

 

 

 

 

 

그럼 다시 아까로 돌아와서 다음과 같은상황에서

3번이 2번을 삭제하고, 1번도 순차적으로 삭제할 수 있다는 말이 된다.

그럼 지금 상황은 1번선이 현재선인 상태 -> 3번선과 2번선의 교점 이후 2번선 삭제 , 1번선 삭제 ->1번선이 현재선인데 1번선이 삭제되었으므로, 3번선으로 업데이트,

이런식으로 된다.

 

이것을 일반화 하면 , 

 h가 증가함에 따라 1번선과 2번선의 교점 저장, 2번,3번 교점 저장, .. 이렇게 계속해서 저장해 나가고,        h가 증가함에 따라 n, n - 1교점에 도달하게 되면  n-1번째 이하 의 선들중 살아남은 선들을 순차적으로 삭제해 나가고,  이제 더이상 삭제할 수 없을 때는 그 삭제할 수 없는 선과의 교점을 저장하여  다시 그 교점에 도달했을 때 그 교점부터 또 순차적으로 삭제해 나가면 된다.

 

즉 새로운 hn에 도달할 때마다 n번째 직선이 생겨나고, n, n - 1번째 직선의 교점을 저장한다.  또 hn일때 저장되었던 삭제 가능한 선을 삭제하고, 그 밑의 선들을 순차적으로 삭제해 나간다. 이렇게 하면 교점은 n, n - 1번째만 저장하고도, 삭제가능한 모든 선을 삭제할 수 있다.

즉 핵심은 n번째 선은 n-1번째 선을 삭제하기 전까지는 어떤 선도 삭제할 수 없기 때문에 n,n-1교점에 도달한 시점부터는 순차적으로 쭈루룩 삭제가 가능하다.  가능한 만큼 삭제하고, 다음선은 또 교점을 저장해 다음 h에서 삭제해나가면 된다.

따라서 n,n-1교점만 저장해도 된다.

 

이런식으로 선을 h마다 생성하고, 삭제가능한만큼 삭제하고, 삭제 후 현재선이 삭제된 경우 다음 선으로 업데이트 해나가는 과정을 거치면 O(n)에 해결이 가능할 것이다. 물론 O(n)에서 계산은 좀 복잡해 좀 더 걸리겠지만...

나같은 경우는 최적화 문제인지 1초나 걸렸다..

 

눈물의 동고쇼 현장...

 

이문제를 푸는데 너무 큰 정신적 피해를 입었으므로 당분간은 고난도 문제를 쉬어야 겠다...

이제 class3 대충 마무리 하면 플레5로 승진할 것 같다.

2달정도만에 실버에서 플레로 갔긴 했지만..  취준에 도움이 될지는 모르겠다.. ㅋㅋ 개발공부에 이제 좀 더 비중을 높여야겠다