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

문제

koosaga와 cubelover가 "핌버"를 하고 있다. 핌버는 님 게임에 규칙을 추가한 게임이다. 핌버는 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 핌버를 진행한다. 각 사람의 턴이 되면, 돌 더미 하나를 선택해 돌을 제거한다. 제거한 돌의 개수는 피보나치 수여야 한다.

 

전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. 

 

게임은 koosaga가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람을 출력한다.

 

 

입력

첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 105)이 주어진다. 둘째 줄에 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 3×106)가 주어진다.

 

 

출력

koosaga가 이기는 경우에는 "koosaga"를, cubelover가 이기는 경우에는 "cubelover"를 출력한다.

 

 

풀이

다이나믹 프로그래밍과 그런디 수를 이용하여 풀 수 있는 문제였습니다.

 

이 문제를 풀기 위해서 선행되는 과정이 2가지가 있습니다.

우선 "11898번 님게임 2" 를 통해서 필승 전략이라는 것이 무엇인지 알아야 하고, '그런디 수' 라는 이론을 이해하고 있어야합니다.

 

먼저, 위의 문제를 풀어보지 않으신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 11868번 : 님 게임 2 (JAVA)

 

 

그런디 수를 아직 잘 모르시는 분은 아래 포스팅 2개를 꼭 정독하셔야 합니다.

 

 

nim game과 grundy number

 

 

BOJ 게임 문제 스페셜

 

 

그런디 수를 구하기 위해서는 특히, 아래 식을 잘 이해하고 있어야합니다.

 

 

여기서 mex는 "다음 상태의 그런디 수 중 존재하지 않는 가장 작은 0을 포함한 양의 정수" 입니다.

 

님 게임을 예로 설명드리겠습니다.

돌 더미에서 돌이 0개인 경우, 1개인 경우, ... n개인 경우를 예로 들겠습니다.

 

돌이 0개인 경우는 기저 사례로 G₀ = 0 입니다.

 

돌이 1개인 경우, 다음 상태는 돌이 0개 밖에 없습니다.

0의 그런디 수는 0이므로 G₁ = 1 입니다.

 

돌이 2개인 경우, 다음 상태는 돌이 1개, 0개 입니다.

0의 그런디수는 0, 1의 그런디수는 1이므로 G₂ = 2가 됩니다.

 

이를 일반화하면, G_n = n 이라는 사실을 알 수 있습니다.

그리고 돌 더미가 여러 개일 경우, 님 게임의 필승 전략과 같이 모든 돌 더미의 그런디 수를 XOR 하여 0이면 후공이 승리, 0이 아니면 선공이 승리합니다.

 

위 로직을 이해하였으면, 이 문제도 충분히 풀 수 있습니다.

다만, 돌을 피보나치 수만큼 빼야한다는 사실만 주의하면 됩니다.

이 부분도 예시를 들어 나열해 봅시다.

 

먼저, 돌 더미의 돌이 0, 1, 2, 3 까지는 모두 피보나치 수에 속하므로

G₀ = 0, G₁ = 1, G₂ = 2, G₃ = 3 이 되는 것은 자명합니다.

 

이제, 돌이 4개일 경우부터 주의 깊게 살펴보아야 합니다.

돌이 4개일 때, 다음 상태는 돌이 3개, 2개, 1개입니다.

그리고 G₁ = 1, G₂ = 2, G₃ = 3 이므로 mex를 취하여 G₄ = 0 이 되는 것을 알 수 있습니다.

1, 2, 3 중에 존재하지 않는 가장 작은 0을 포함한 양의 정수는 0이기 때문이죠.

 

마찬가지로, 돌이 5개일 때, 다음 상태는 4개, 3개, 2개, 0개 입니다.

그리고 G₀ = 0, G₂ = 2, G₃ = 3, G₄ = 0 이므로 mex를 취하여 G₅ = 1 이 되는 것을 알 수 있습니다.

0, 2, 3 중에 존재하지 않는 가장 작은 0을 포함한 양의 정수는 1이기 때문이죠.

 

이제, 우리는 피보나치 수만큼 돌을 빼는 님 게임의 그런디 수를 구하는 방법을 이해하였습니다.

코드로만 옮기면 끝인데, 한 가지 어려운 부분이 있습니다.

 

바로, mex를 구하는 과정이죠. 정의 자체는 쉽지만, 이를 효율적으로 코드를 짜는 것은 만만치 않습니다.

가장 처음 생각해 볼 수 있는 코드는 아래와 같습니다.

 

 

 

 

Set에 피보나치 수만큼 돌을 뺀 그런디 수를 넣어 놓고, mex를 0부터 시작하여 Set에 mex가 존재하지 않는 순간을 포착하면 됩니다.

그리고 이대로 코드를 짜서 1 ~ 3000000 까지의 그런디 수를 저장하는 배열을 정의한 후, 이 배열을 사용하여 문제의 input에 맞게 XOR 합을 구하면 끝이긴 합니다.

 

아래는 Set 방식으로 그런디 수를 구하는 과정입니다.

 

 

 

 

하지만, Set을 생성하고 add하고 contains 하는 과정이 느립니다.

여기서 시간을 줄이는 방법은 간단합니다.

바로, 1 ~ 3000000 까지 가장 큰 그런디 수를 찾고, 0 ~ maxGrundyNum 까지만 저장하는 boolean[] 타입의 배열(check)을 만드는 것입니다.

 

이 문제에서 가장 큰 그런디 수는 15 였기 때문에 16칸을 저장하는 check를 생성하고, 특정 돌 더미의 돌을 피보나치 수만큼 빼 보면서 해당하는 그런디 수를 check에서 true 처리를 해 주면 됩니다.

 

그리고 mex를 구할 때는 mex를 0에서 시작하여, check[mex] = false 가 되는 순간을 포착하면 됩니다.

이후로는 위에서 설명한 대로 1 ~ 3000000 까지의 그런디 수를 저장하는 배열을 정의한 후, 이 배열을 사용하여 문제의 input에 맞게 XOR 합을 구하고, XOR 합이 0이면 "cubelover", 0이 아니면 "koosaga"를 출력하면 끝입니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

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