[BOJ] 백준 2600번 : 구슬게임 (JAVA)

문제

두 사람 A와 B가 번갈아 가면서 두 개의 구슬 통에서 몇 개씩의 구슬을 꺼내는 게임을 한다.

 

한번에 한 사람이 한 통에서 꺼낼 수 있는 구슬의 개수는 세 가지 뿐이다. 그리고 구슬을 꺼낼 경우 두 개의 구슬 통 중에서 하나를 마음대로 선택해서 그 안에서만 꺼낼 수 있다. 즉 두 개의 통 모두에서 동시에 몇 개씩 꺼낼 수는 없다.

 

게임은 항상 A가 먼저하고 그 다음 B, 그 다음 A 순으로 번갈아가면서 진행된다. 그리고 자신의 차례 가 되었을 때에 정해진 규칙대로 구슬을 꺼낼 수 없는 사람이 게임에서 지게 되고, 상대방은 승리하게 된다.

 

예를 들어 한번에 꺼낼 수 있는 구슬의 개수를 1개, 3개, 또는 4개라고 하자. 만일 두 개의 구슬 통 에 각각 4개, 1개의 구슬이 있다고 하면 처음 선택을 하게 되는 A가 이긴다. 그러나 만일 두 통속의 구슬이 각각 5개, 5개라면 B가 이긴다.

 

즉 한번에 꺼낼 수 있는 구슬 개수인 b1 , b2 , b3가 주어지고, 두 구슬 통 속에 들어있는 구슬의 수 인 k1, k2이 정해지면, 이러한 b1 , b2 , b3와 k1, k2에 따라서 승패는 결정된다. 문제는 주어진 b1 , b2 , b3와 k1, k2에 대하여 A, B중 누가 승자인지를 결정하는 것이다.

 

처음 두 통 속에 들어 있는 구슬의 수 k1, k2와 한 번에 꺼낼 수 있는 구슬의 수 b1 , b2 , b3에 대 한 제한조건은 다음과 같다.

 

 

1≤b1 < b2< b3 ≤30 

1≤k1, k2 ≤500

 

 

입력

첫 줄에는 한번에 꺼낼 수 있는 구슬의 개수를 나타내는 세 개 의 정수 b1 , b2, b3 가 나타난다. 그 다음 5개의 각 줄에는 두 통속에 처음 담겨있는 구슬의 개수 k1, k2가 각각 표시되어 있다.

 

 

출력

각 5개의 k1 , k2 경우에 대하 여 그에 대응되는 승자(A 또는 B)를 각각 한 줄에 하나씩 차례대로 다섯 개를 출력해야 한다.

 

 

풀이

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

 

이 이론을 잘 모르시는 분은 아래 포스팅을 꼭 읽어보고 오시길 바랍니다.

 

 

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

 

 

스프라그-그런디 정리는 현재 상태에 대해서 다음 상태가 될 수 있는 경우는 무엇이 있는지 따지는 것이 중요합니다.

또한, 다음 상태를 고려하여 그런디 수를 구해야 하는데, 그런디 수는 mex를 이용하여 구할 수 있습니다.

 

 

 

 

 

일단, 문제의 예시로 위 정리를 적용해 보겠습니다. 

 

 

<문제의 예시>

 

b1 = 1, b2 = 3, b3 = 4.  -> 가져갈 수 있는 구슬의 개수

 

 

 

N = 0인 경우, G₀ = 0

 

N = 1인 경우, 다음 상태는 N = 0 밖에 없고, G₀ = 0이므로 G₁ = 1이 됩니다.

 

N = 2인 경우, 다음 상태는 N = 1 밖에 없고, G₁ = 1이므로 G₂ = 0이 됩니다.

 

N = 3인 경우, 다음 상태는 N = 0, 2가 있고, G₀ = 0이고, G₂ = 0이므로 G₃ = 1이 됩니다.

 

 

결과적으로, G_N = mex(G_{N - b1}, G_{N - b2}, G_{N - b3}) 이 된다는 사실을 알 수 있습니다.

단, N - b_i를 한 값이 0보다 크거나 같아야 합니다.

 

따라서, 문제에서 b1, b2, b3를 입력받은 후, 위에서 정의한 점화식을 활용하여 mex에 따른 값을 dp에 저장해 준뒤, 5개의 입력 케이스에 대해서 출력을 하면 됩니다.

 

 

이제, mex를 구해야 하는데, 위의 포스팅에서 언급했듯이 아래와 같이 mex를 구할 수 있습니다.

 

 

 

 

하지만 위의 방식대로 mex를 구하면, set을 생성하고, set에 dp 값을 집어넣고, contains로 비교하는 과정이 느립니다.

따라서, set보다는 boolean[] 타입의 배열을 정의하는 것이 빠릅니다.

 

이 문제에서 그런디 수는 최대 3인 것을 확인하였습니다. 따라서 길이가 4인 boolean[] 타입의 배열을 만들고, 위의 set 방식과 유사하게 mex를 구하는 코드를 짜면 됩니다.

 

 

b1, b2, b3에 따른 그런디 수를 할당한 dp 배열을 정의하였다면, 이제 거의 끝났습니다.

마지막으로, 입력값 k1, k2에 대해서 A와 B 중 누가 이기는지 결정지으면 됩니다.

방식은 간단합니다. dp[k1] ^ dp[k2] 가 0이면 B가 이기고, 0이 아니면 A가 이깁니다.

 

 

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

 

 

소스코드

 

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