[BOJ] 백준 16895번 : 님 게임 3 (JAVA)

문제

구사과와 큐브러버가 님 게임을 하고 있다. 님 게임은 돌을 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가면서 님 게임을 진행한다. 각 사람의 턴이 되면, 돌이 있는 돌 더미를 하나 선택하고, 그 돌 더미에서 돌을 하나 이상 제거한다. 전체 돌 더미에서 마지막 돌을 제거하는 사람이 게임을 이기게 된다. 

 

게임은 구사과가 먼저 시작한다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 구사과가 게임을 이기기 위해서 첫 턴에 할 수 있는 방법의 수를 구하시오.

 

 

입력

첫째 줄에 돌 더미의 개수 N (1 ≤ N ≤ 1000)이 주어진다.

둘째 줄에는 각 돌 더미에 쌓여있는 돌의 개수 Pi (1 ≤ Pi ≤ 1000)가 주어진다.

 

 

출력

구사과가 게임을 이기기 위해서 첫 턴에 할 수 있는 방법의 수를 출력한다.

 

 

풀이

님 게임의 필승 전략을 사용하여 풀 수 있는 문제였습니다.

 

마지막 돌을 가져가는 사람이 이기는 규칙이므로 "11694번 님 게임 2" 문제와 상당히 유사합니다.

혹시 위 문제를 풀어보지 않은 분은 아래 포스팅을 꼭 정독하시길 바랍니다.

 

 

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

 

 

이번 문제는 단순히 선공이 이기는지 후공이 이기는지 판별하는 것이 아니라, 선공이 이기는 경우의 수를 구하는 것이 관건이었습니다.

 

앞서 포스팅의 문서를 읽으셨으면, 선공이 이기는 필승 전략은 "님 합을 0으로 만든다."임을 알고 계실 겁니다.

따라서, 각 돌 더미의 돌 개수를 1개씩 빼 보면서 님 합이 0이 되는 경우를 체크하면 됩니다.

 

단, 초기 돌 더미의 님 합이 0일 경우, 무조건 패배하므로 경우의 수는 0이 된다는 사실을 주의하셔야 합니다.

N과 P의 크기가 1000으로 크지 않은 수 이기때문에 위와 같은 브루트포스를 수행해도 AC를 받을 수 있습니다.

 

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

 

 

소스코드

 

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