[BOJ] 백준 20004번 : 베스킨라빈스 31 (JAVA)

문제

베스킨라빈스 게임은 1부터 31까지의 수를 순차적으로 한번에 1~3개까지 연달아 부를 수 있으며, 마지막 31을 부른 사람이 지는 게임이다. 시온이와 민우는 베스킨라빈스 게임을 하기로 했지만 이 게임이 너무 유명한 나머지 시온이와 민우 모두 필승 방법을 알고 있었다.

 

평소에 항상 운이 없던 시온이는 가위바위보를 져 민우에게 선공을 빼았기게 되었고 이대로 게임을 한다면 질 수밖에 없는 상황이다. 그래서 시온이는 1~3개의 수가 아닌 1~n까지의 수를 부를 수 있는 규칙의 게임으로 변형하자고 말하였고 민우도 수락했다.

 

이 경우 시온이가 게임을 이길 수 있는 모든 n(1 ≤ n ≤ A)을 출력하시오.

 

 

입력

첫 번째 줄에 A이 주어진다. (1 ≤ A ≤ 31)

 

 

출력

각 줄에 시온이가 게임을 이길 수 있는 n을 한 줄에 하나씩 오름차순으로 출력한다.

 

 

풀이

간단한 게임 이론 문제였습니다.

 

 

누구나 한 번쯤 다 해 보았을 유명한 '베스킨라빈스 31' 문제였습니다.

우리는 흔히 1, 2, 3 중 하나를 부를 수 있다는 규칙으로 위 게임을 즐겼지만,

이 문제에서는 1 ~ n (1 <= n <= 31) 중 하나로 부를 수 있다는 규칙으로 바뀌었습니다.

 

그리고 문제에서 시온이가 이기는 경우를 구해야하는데, 시온이는 후공에 해당됩니다.

따라서, 후공이 이길 수 있는 일명 '필승 전략'을 찾아야 합니다.

 

 

예를 들어, n이 3이라고 해 봅시다.

그렇다면, 단순히 '필승 전략'은 다들 잘 알다시피 '30, 26, 22, ... , 2' 를 부르는 사람이 이기게 됩니다.

 

31을 부르는 순간 패배이므로 그 바로 전인 30을 부르는 사람이 이기는 것인데, 이를 다시 생각하면 30을 불러야 이기는 것이므로 상대방이 30을 부르지 못하게 해야 합니다. 이와 같은 로직을 반복하면 맨 처음에 선공이 2를 부르면 항상 게임에서 승리하는 것입니다.

 

 

위의 내용을 조금 일반화하자면, 필승 전략은 '30, 30 - (n + 1), 30 - 2 * (n + 1), ... , 30 % (n + 1)' 를 부르는 사람이 이기게 됩니다. 여기서, 30 % (n + 1)에 주목해야 합니다.

 

 

(1) 30 % (n + 1) != 0

30 % (n + 1)의 나머지가 0이 아니라면, 선공이 첫 턴에 30 % (n + 1) 수를 부를 수 있다는 것을 의미합니다.
따라서, 이 경우 후공은 이길 수 없습니다.

 

 

(2) 30 % (n + 1) == 0

30 % (n + 1)의 나머지가 0이라는 말은, 선공이 첫 턴에 수를 아무것도 부르지 않아야 한다는 뜻인데, 수를 적어도 1개는 불러야 합니다. 따라서, 후공은 0 다음의 필승 전략 수를 차례로 부르면서 선공이 31을 부르도록 강제하여 이길 수 있게 됩니다.

 

 

우리는 2번째 조건이 되는 1 <= n <= A 인 n을 모두 출력하면 됩니다.

간단한 반복문과 조건문으로 해결되기 때문에 이와 관련된 내용은 아래 소스코드를 참고하시기 바랍니다.

 

 

소스코드

 

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