[diamond5][해설안봄, 알고리즘 분류 안봄] 28436 돌 옮기기

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

 

 

경비병 세우기 게임에 이어 2번째 게임이론 문제를 풀어보았다. 어떻게 하면 서로가 최선을 다할 수 있게 플레이하는지는 어렵지 않게 생각 할 수 있었지만, 이 과정을 어떻게 하면 간소화 시킬수 있을지(시간제한 안에 맞출 수 있을지) 생각하는게 까다로웠다.

특히 디버깅 할때 단순 자료형 실수 였음에도 내가 잘못 풀었나 로직부터 찬찬히 뜯어보며 고통스러운 시간을 보냈다.. 아무리 생각해도 맞는 것 같은데 그렇다고 100프로 확신은 못하는 괴로움이란....

 

이 문제를 풀기 위해선 어떻게 해야 최선을 다하는 건지 알아야 한다.

우선 내가 돌을 왼쪽으로 옮길 때, 상대방도 돌을 옮길 기회를 얻는 건지를 파악해야 한다.

만약

 

       .B......W.W...W..B

        1       1    2   3

 

이렇게 있을 때 가장왼쪽의 1번 W를 왼쪽으로 옮겨도 B가 돌을 더 옮길 수 있는 기회는 없다.  가장 오른쪽의 W가 방패막이(?)를 하기 때문이다.

2번 W도 마찬가지 이지만, 3번 W일때는 다르다. 3번 W를 왼쪽으로 한칸씩 옮길때마다 B도 옮길 수 있는 칸이 한칸 씩 늘어나게 된다.  1,2번 W는 의심없이 옮길 수 있지만 3번 W는 일단 두도록 하자.

이런식으로 연속된 같은 타입의 돌에서는 맨 오른쪽 돌을 제외하고 모두 왼쪽으로 가능한 만큼 옮길 수 있다.

즉 옮기고 나면 이렇게 될 것이다.

   .BWWW...........B

 

간단하게 생각해보면 n번째 돌일때 n + 1번째 돌과 종류가 같을 경우 마음껏 옮길 수 있다. 

 

이번에는 자기 뒤에 다른 종류의 돌이 여러개 있는 경우를 생각해 보자.

 즉 1번 B 의 경우이다.  B를 왼쪽으로 옮기게 되면 뒤에있는 1~3번 W에게 기회를 주게되는 셈이 되 버린다. 정확히 말하면  3번W는 옮길지 확실하지 않아서, 안전하게 1번,2번 W는 확실히 옮길 수 있다.    B를 한칸 옮길 때마다 W는 1번W, 2번W 각각 한칸씩으로 총 2칸을 옮길 수 있게 되는 셈이므로 절대로 1번 B는 옮기면 안된다.

....BWW.....................B

 다음과 같이 뒤에 W가 2개있는 경우라도 오른쪽 W는 방패로 세우고 B가 옮기는 만큼 W도 옮길 수 있다. 

B ->W -> B-> W.... 순서로 가서 결국엔 W로 끝나므로 B의 순서일때 돌을 옮길 수 없다.

 

결국 B는 뒤에 W가 2개이상이면 무조건 옮기면 안된다. 

 

...WBB........... 이경우 W도 마찬가지로 옮기면 안된다. 

 

 

 

 

가장 골치 아픈 경우는 B뒤에 W가 1개만 있을 경우이다.

 ....B....W...B.....W...B...W.......B...B.....

이러한 경우이다.

 이런 경우는 B 한개를 한칸 옮기면 W 도 한개만 옮길 기회가 생기는 것이므로, 서로 쌤쌤이 되는 것 같다. 그럼 옮겨도 그만 안옮겨도 그만인걸까? 

 이부분에 대해 좀 관찰을 해보았는데 그렇지 않았다.

 

우선 다음과 같은 경우를 생각해보자

......W...B...W...B...W

      1    1    2   2      3 

다음과 같은 경우를 생각해보자.

 우선 1번 W를  옮길때마다 B도 같이 옮긴다 생각하면

W....B.........W...B...W 이렇게 되고, 2번W, 2번B도 마찬가지로

W....BW...B............W 이렇게 된다.

B의 차례에서 끝나므로 다시 W의 차례이고,     3번W와  2번B와의 거리만큼 옮길 수 있게 된다. 즉 여유분이 생기는 것이다.

만약1번B가 W가 이득을 보는걸 참다못해 돌을 옮기면 2번 W도 그에 반응해 옮길 수 있다.

WBW.......B............W 이런식으로 될 것이다.  

2번B도 옮기게 되면 W도 마찬가지로 반응해서

WBWB............W....... 이렇게 될 것이다.

그런데 사실 2번B와 3W의 거리는 B가 가만히 있을 때 W를 가능한만큼 옮길 수 있는 횟수가 된다. 

 B가 자기가 옮겨봤자 이득이 되지 않아 가만히 있다고 치면 W가 그만큼 옮길 수 있게 되는 것이다.

 

 W........BW......BW... 즉 이런식으로 될 것이다.

 

......W...B...W...B...W

      1    1    2   2      3 

  즉 여기서 W의 여유분은         0   ~ 1번 W  +  1번B ~ 2번W  + 2번B~3번W가 되는 것이다.

 

 

이렇게 다른종류 돌이 한개씩 번갈아 가며 있을 때는 무조건 마지막 돌의 플레이어가 여유가 생기고, 옮길 수 있는 만큼 여유가 생기게 된다.

 

 

이제 이사실을 실전에서 써보자.

 ....B....W...B.....W...B...W.......B...B.....

     1     1    2      2   3   3        4     5

 

이 상황에서  아까 설명한 것 처럼 3번 W는 W플레이어 입장에서 절대로 옮겨서는 안된다. 

그렇다면 1번B,1번W,.... 3번B 까지는 옮길 수 있을 것이다.  3번 B가 맨 마지막이므로, 무조건 B에게 여유가 생기는 상황이고,W가 가만히 있을 때 B가 이동할 수 잇는만큼 여유가 생기게 된다. 4 + 3 + 3 = 10만큼 B는 여유가 생기게 된다.

 

 

정리하면 이렇다.

 

1. 바로 다음돌이 같은 종류일 경우, 가능한 만큼 이동할 수 있는 여유분 획득. 

2. 다음돌이 연속된 다른종류의 돌일 경우, 절대로 움직일 수 없음

3. WBWBWBWB... 혹은 BWBWBWBW.... 가 연속될 경우,  rule2번에 의해 연속을 끊어야 하고, 그 때의 마지막 돌의 종류가 이동 가능한 돌 수만큼 여유분 획득

 

4. 예외로, 마지막 돌의 경우, 1번과 같은 규칙 적용 (뒤에 간섭할 돌이 더이상 없기 때문)

 

 

 

이렇게 생각해 놨는데,  코드를 좀 복잡하게 짜놔서 맞을 거란 기대는 안하고 채점을 돌렸는데,,, 31퍼센트 정도까지 진행되다 틀려버렸다... 이정도까지 진행되었으면 아이디어는 맞는 것 같은데 예외처리 문제인가... 아무리 생각해도 떠올린 건 돌의 수가 1개일 경우와 문자열길이가 1 일때였으나,. 문제 제한상황에서 다 필터링 될 상황이였고... 멘붕하던 도중  여유분을 세는 배열이 int인걸 발견했다. 문자열 길이가 짧다고 생각해와서 설마 여유분이 int를 넘어갈거라는 생각은 하지도 못했는데... 50만개라 생각해보니 충분히 가능하였다.  long으로 바꾸니 바로 정답 처리....

그 동안 자료형에 그토록 호되게 당했으면서 이번에도 또 방심해 버렸다... 이제 코테 풀때는 무조건 long으로 하는 습관을 들여야겠다..