[BOJ] 백준 13034번 : 다각형 게임 (JAVA)

문제

N개의 꼭짓점으로 이루어진 볼록 다각형이 있다. 다각형의 내각은 모두 180보다 작다. 꼭짓점은 1부터 N번까지 시계 방향으로 번호가 매겨져 있다.

 

성관이와 홍준이는 다각형에서 게임을 하려고 한다. 성관이가 먼저 턴을 갖는다.

 

각 턴마다 플레이어는 두 꼭짓점을 고르고, 선분을 긋는다 (변과 일치해도 된다). 이때, 이미 그려져 있는 선분과 교차하면 안 된다 (선분의 끝 점에서 겹치는 것도 교차하는 것이다). 더 이상 선분을 그릴 수 없는 사람이 게임을 패배한다.

 

N이 주어진다. 두 사람이 최적의 방법으로 게임했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N (3 ≤ N ≤ 1,000) 이 주어진다.

 

 

출력

성관이가 이기면 1, 홍준이가 이기면 2를 출력한다.

 

 

풀이

스프라그-그런디 정리를 이용하여 풀 수 있는 문제였습니다.

 

 

위 이론을 모르시면 이 문제를 풀 수 없으므로 아래 포스팅을 꼭 먼저 읽어보고 오시길 바랍니다.

 

 

[BOJ] 백준 16877번 : 핌버 (JAVA)

 

 

먼저, dp[0] = dp[1] = 0으로, dp[2] = 1, dp[3] = 1로 초기값을 세팅해 줍니다.

 

그리고 mex를 구하기 위해서 다음 상황을 정의해야 합니다.

 

간단합니다. 특정 점에서 직선을 하나 긋는 순간, 게임판이 하나에서 두 개로 나뉘게 됩니다.

 

예를 들어 5각형이 있다고 합시다.

 

 

 

 

그렇다면, 직선 하나를 그음으로써 위와 같이 0각형 게임판과, 3각형 게임판 2개로 나뉜다는 것을 알 수 있습니다.

 

3각형 게임판이 되는 이유는, 어떤 직선도 교차해서는 안 되기때문이죠.

 

위와 같은 방식으로 다음 상황을 전개하면, (0, 3), (1, 2) 이 됩니다.

 

그리고 게임판이 2개로 나뉘었을 때는 XOR합을 취해야 합니다.

 

위의 예시에서는 다음 상황의 그런디 수는 각각 dp[0] ^ dp[3] = 0 ^ 1 = 1, dp[1] ^ dp[2] = 0 ^ 1 = 1로, mex는 0이 된다는 사실을 알 수 있습니다.

 

따라서, dp[5] = 0 이므로 5각형일 때 후공이 승리합니다.

 

위와 같은 방식으로 스프라그-그런디 정리를 활용하면 풀 수 있습니다.

 

자세한 내용을 아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

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