[platinum4][풀이,분류 미확인] boj32111 관광코스

재미있는 애드 훅 문제였다.

 

아이디어를 떠올리기만 하면 원형일 때를 고려해 구현에 살짝 까다로웠지만 어떻게든 풀 수 있는 문제이다.

우선 가장 먼저 생각할 수 있는 아이디어를 떠올려보자.

 

원형 중에 무조건 + 를 배치해야 하는 곳은  O가 존재하는 곳이다. 즉 O일때 그사람이 만족도가 1이상으로 유지하면서 한바퀴돌려면, 반드시 처음 시작할 때 + 여야 한다.  -이면 시작과 동시에 0이 되므로, 만족도 1이상 유지가 불가능 하기 때문이다.

아래와 같이 O이면 반드시 + 이다.

 

자 이제, 그럼 나머지 X인 부분들을 + 또는 -로 채워야 한다.

우선, 3번, 4번, 5번을 살펴보자. 3,4,5번은 한바퀴돌았을 때 만족도 1이상 유지에 실패해야 한다. 반면 그 전에 있는 1번, 2번은 성공해야 한다.

 3번 , 4번 ,5번을 모두 -로 두면 당연히 3~5번은 1이상 유지 실패하겠지만,  1,2번또한 실패하게 된다. 

그럼 들 수 있는 생각이  3,4,5 번중 적당하게 + 를 두어 1,2번모두 일단 호감도를 적당하게 높인 뒤, 3,4,5번이 모두 실패할 정도로 그 뒤엔 -를 배치하면 될거라는 생각이 든다. 

또한 3,4,5번에 대한 문제는 반드시 5번이 지나기 전에 끝내야 한다. 즉, 시계방향으로 돌때 5번이 지나기전까진 3,4,5번을 호감도 0으로 만들어야 한다. 그 이유는 무엇일까?

 

 6,7 번은 반드시 성공시켜야 한다.  6번은 호감도 1인상태에서 시작해 한바퀴 돌때 호감도 0이상이여야 한다.  그런데 3,4,5번이 5번까지 돌때 실패하지 않았다면, 6번에서는 호감도가 당연히 1이상인 상태고, 결국 3,4,5번은 반드시 성공할 수밖에 없다.

 

이점을 생각하며, 3,4,5번에서 실패하게 만들 아이디어를 내보자.

 

위와 같이 둔다면, 3번은 호감도 1인 상태로 시작해 3번에서 호감도 2 , 4번에서 1 , 5번에서 0 인 상태로 끝날 것이다.

3번이 5번에서 호감도 0이되므로, 그 이전인 1,2번은 당연히 호감도가 1이상이 될 것이다. 

 즉 OOOXXXX... XXXO 이렇게 있을 때 연속된 X구간의 가장 왼쪽부분이 X구간의 맨 오른쪽까지 갔을 때 호감도가 0이 되도록 만든다면, 그 이전의 O(1번,2번,3번)은 모두 호감도가 1이상이 될 것이다.  또한 다른 x구간들은 모두 호감도가 0미만이 될것이다.

 

위와 같은 경우 맨왼쪽 x(4번)부터 맨왼쪽 X까지 +를 연속해서 3개, -를 그후 4개를 두면 정확히 만족도를 0으로 만들 수 있다. 

1번부터 만족도가 3 , 2 , 1, 0, -1 .... 이 될 것이다.

 

눈치챘을 수도 있겠지만, 이 경우는 연속된 x구간의 길이가 홀 수 일때만 가능하다.

 

X구간의 길이가 짝수 일떼는 답을 만들 수 없다.

 

다음과 같이 x구간에서 + 가 3개, - 가 5개로   x구간의 총합이 -2인 상황을 생각해보자. 이렇게 되면 3번은 실패할 수밖에 없다.  3번까지 성공하게 하려면,  x구간에 + 4개, - 4개로 총합이 0이되게 만들 수 밖에 없다.   X구간의 + 를 더 늘리는 것은 X구간이 성공할 가능성을 높이는 것이므로 안된다.

 

따라서 +4 개 , - 4개일때도 X구간중 적어도 한 곳이라도 성공할 수밖에없는 것을 증명하면 된다.

 

 

우선 다음과 같을 때는 첫번째 x가 성공한다. 첫번째 x를 실패하기 위해서는  그다음 총합이 -1이 되게 배치해야된다 (+ 0개, - 1개).(+1개, - 2개), (+2개, -3개) 등...

 

다음과 같이 첫번째를 실패시키기 위해선 빨간 네모 처럼 배치해야 한다. 그런데, 그렇게 되면 그뒤는 + 4개 , -3개 or

+ 3개 - 2개로 + 가 많게 된다.

 

왼쪽과 같은 경우, 두번째 X를 실패시키기 위해  +1개, -2개 를 배치하였다,

오른쪽은 2,3번째 X는 자연스럽게 실패하게 되고, 4번째 X를 고려하면 +1개 -2개를 배치하였다. (물론 + 0개, - 1개 와 같은 배치도 가능) . 어쨌거나 공통적인 점은 실패시키기 위해 배치할 수록, 배치 되지 않은  + - 중  +갯수가 많아진다는 것이다.

(왼쪽의 경우 + 3개, - 1개, 오른쪽 경우 + 4개)  즉 , 점차 배치할 수록 + 가 많아질 수밖에 없고, 오른쪽 으로 갈수록 결국 적어도 한곳은 성공할 수밖에 없게 된다.

 

 

요약하자면 다음과 같다.

 

1. O인 곳은 무조건 + 배치

2. 그외 연속된 X구간길이가 홀수 라면 ,  X구간 시작부터 len / 2 까지는  + 배치, 그 뒤는 전부  -배치.

3. X구간길이가 짝수인 곳이 한군데라도 있으면 해를 구성할 수 없다.