[BOJ] 백준 17080번 : 결함 게임 (JAVA)

문제

택희와 현우는 게임을 하나 하려 한다. 이 게임은 보드판 하나와 N개의 크기가 서로 다른 돌들을 이용해 진행된다. 게임의 규칙은 아래와 같다.

 

 

• ‘돌탑’ 이란, 크기가 가장 큰 돌이 아래, 가장 작은 돌이 위에 오도록 크기 순으로 정렬되어 쌓인 돌무더기를 의미한다.

 

• 처음엔 크기가 1, 2, …, N인 돌 하나씩과 비어 있는 보드판 하나를 가지고 시작하며, 서로 번갈아가며 보드판에 새로운 돌탑의 바닥을 만들거나 보드판 위에 있는 기존의 돌탑 위에 돌 하나를 올려놓는 식으로 진행된다. 각 크기의 돌은 하나씩밖에 없으며, 두 플레이어가 공유한다. 각 돌은 한번 보드판 위에 올라간 이후엔 아무도 손댈 수 없다.

 

• 각 플레이어는 턴마다, 만약 현재 보드 위에 있는 돌탑 중 어딘가에 올릴 수 있는 돌이 남아있다면, 반드시 그러한 돌들 중 하나를 골라 올릴 수 있는 돌탑 중 원하는 돌탑 위에 올린다.

 

• 만약 어떤 돌탑에도 돌을 올릴 수 없다면, 남아있는 돌 중 아무거나 하나를 골라 보드 위에 새로운 돌탑의 바닥을 만든다.

 

• 모든 돌이 소진된 뒤, 돌탑의 개수가 홀수이면 선공이 이기며, 짝수이면 후공이 이긴다.

 

 

택희와 현우는 게임을 하기 위해 N개의 크기가 서로 다른 돌을 모았다. 둘은 항상 최선을 다하며, 이길 수 있는 상황에선 반드시 이긴다고 가정할 때, 이 게임의 승자는 누가 될까?

 

 

입력

첫째 줄에 돌의 개수 N이 주어진다. (1 ≤ N ≤ 5,000,000)

 

 

출력

선공이 이긴다면 1을, 후공이 이긴다면 2를 출력한다.

 

 

풀이

꽤나 까다로웠던 게임 이론 문제였습니다.

 

 

저는 게임 이론 문제를 풀 때, 다음 상황을 정의하고 그 상황들 중 패배하는 경우가 하나라도 있으면 현재 상황은 이기고, 다음 모든 상황들이 승리한다면, 현재 상황은 지는 로직을 이용합니다.

 

 

하지만, 이 문제는 돌탑을 쌓는 다음 상황을 정의하기 어려워서 단순히 규칙을 찾기 위해서 노력을 하였습니다.

먼저, 규칙부터 말씀드리겠습니다.

 

 

N = 3, 7, 11, ... 과 같이 4의 주기로 후공이 승리합니다.

아주 단순하죠? 이제 증명해 봅시다.

 

 

우선, N = 3, 7, 11, ... 외에 N이 승리하는 조건을 설명하겠습니다.

 

예를 들어, N = 5 라고 가정해 봅시다.

 

돌은 1, 2, 3, 4, 5가 있을 것입니다. 그리고 선공이 "2번째로 크기가 작은 돌을 뽑는다." 전략을 사용하면 항상 이길 수 있습니다.

 

먼저, 선공이 2로 돌 바닥을 만들면, 후공은 1로 돌탑을 쌓아야 합니다. 그리고 선공이 4로 돌 바닥을 만들면, 후공은 3으로 돌탑을 쌓아야 합니다. 마지막 남은 5로 돌 바닥을 만들면, 돌탑은 총 3개로 홀수가 됩니다.

 

이를 간단히 표현하면, (1 2), (3 4), 5 와 같이 승리하는 것입니다.

 

 

위에서는 N이 홀수일 때를 봤으니, 이번에는 짝수를 봐야 합니다.

N = 4 라고 가정해 봅시다.

 

돌은 1, 2, 3, 4가 있을 것입니다. 필승 전략은 동일한 "2번째로 크기가 작은 돌을 뽑는다."를 사용합니다. 다만, 짝수는 조금 다르니, 주의해서 예시를 보시길 바랍니다.

 

먼저, 선공이 2로 돌 바닥을 만들면, 후공은 1로 돌탑을 쌓아야 합니다. 그러면, 현재 돌은 3과 4가 남습니다.

여기서 4로 돌바닥을 만들면, 후공은 3으로 돌탑을 쌓아서 짝수의 돌탑이 되므로, 3으로 돌 바닥을 만들어야 합니다.

그래야 후공이 4로 또 다른 돌 바닥을 만들어서 돌탑은 총 3개로 홀수가 됩니다.

 

이를 간단히 표현하면, (1, 2), (3), (4) 와 같이 승리하는 것입니다.

 

 

다시, N = 6 이라고 가정해 봅시다.

돌은 1, 2, 3, 4, 5, 6이 있을 것입니다. 필승 전략도 동일하게 적용합니다.

 

위와 같이 간단히 표현하면, (1, 2), (3, 4), (5, 6) 와 같이 승리할 수 있게 됩니다.

 

 

정리하자면, N이 홀수일 때는 "2번째로 크기가 작은 돌을 뽑는다." 전략을 그대로 사용하고, N이 짝수일 때는

"2번째로 크기가 작은 돌을 뽑되, 현재 남은 돌이 2개면 이길 수 있도록 돌탑을 쌓거나 돌 바닥을 만든다."

전략을 사용해야 합니다.

 

 

이제, N = 3, 7, 11, ... 은 왜 항상 선공이 필패하는지 알아봅시다.

물론, 위에서 언급한 필승 전략이 여기서 통하지 않는 것도 맞지만, 다른 모든 경우의 수에 대해서도 패배하는지 증명해야 합니다.

 

 

(1) 선공이 크기가 가장 작은 돌을 뽑는 경우

예를 들어, N = 7이라고 한다면, 후공 입장에서 현재 남은 돌은 2, 3, 4, 5, 6, 7일 것입니다.

 

다시, "후공" 입장에서는 새로운 돌 탑을 쌓아야 하는데, 위에서 언급한

"2번째로 크기가 작은 돌을 뽑되, 현재 남은 돌이 2개면 이길 수 있도록 돌탑을 쌓거나 돌 바닥을 만든다." 

전략을 사용하여 필승할 수 있습니다. 

 

이미 선공이 1로 돌탑을 만든 상태에서 후공이 홀수 개의 돌탑을 만들게 되면, 짝수 개의 돌탑이 만들어지기 때문이죠.

 

 

따라서, 이 경우 선공은 패배합니다.

 

 

(2) 선공이 크기가 가장 작지 않은 돌을 뽑는 경우

예를 들어, N = 7이라고 하고, 선공이 3을 뽑았다고 하면, 후공 입장에서 현재 남은 돌은 1, 2, 4, 5, 6, 7일 것입니다.

 

여기서, 후공이 "크기가 가장 작은 돌을 뽑는다." 전략을 사용하면 필승할 수 있습니다.

후공은 선공이 i번째 돌 바닥을 만들었기 때문에 i보다 작은 돌을 이용하여 돌탑을 쌓아야하는 것은 자명합니다.

하지만, 가장 크기가 작은 돌로 돌탑을 쌓게 되면, 선공 입장에서는 새로운 돌 바닥을 만들어야 합니다.

 

 

후공이 1을 뽑아서 돌탑을 쌓았다면, 현재 남은 돌은 2, 4, 5, 6, 7일 것입니다.

여기서, 선공이 크기가 가장 작은 돌을 뽑게 되면, (1) 과정에 의하여 필패하게 됩니다.

 

그렇다면, 2 이외의 돌을 뽑아서 돌 바닥을 만들어야 하는데 후공이 또, 가장 작은 돌을 뽑아서 돌탑을 만드는 과정을 반복하면 결과적으로 선공 차례에서 돌이 1개 남게 됩니다.

 

이 돌로 돌 바닥을 만들면, 돌탑의 총 개수가 짝수 개가 되므로 선공이 패배합니다.

 

 

여기서, 잠시 제가 내세운 "크기가 2번째로 작은 돌을 뽑는다." 전략을 다시 봅시다.

N = 7 일 경우, (1 2), (3 4), (5 6), 7 과 같이 돌탑의 총 개수가 짝수로 선공이 패배하는 것을 알 수 있습니다.

 

위의 (2) 과정은 선공이 임의의 돌 i를 뽑고, 후공이 크기가 가장 작은 돌을 뽑음으로써, 선공이 위와 같이 돌의 개수가 2개인 돌탑을 쌓도록 강제할 수 있습니다.

 

 

따라서, (1), (2)가 선공이 할 수 있는 모든 경우이고, 그 경우에서 모두 패배하므로 선공은 N = 3, 7, 11, ... 과 같은 4의 주기에서 패배한다고 정리할 수 있습니다.

 

 

이제, 단순한 규칙을 코드로 표현하면 끝입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.