문제

베스킨라빈스 게임은 1부터 31까지의 수를 순차적으로 한번에 1개 이상, 3개 이하 연달아 부를 수 있으며, 마지막 31을 부른 사람이 지는 게임이다. 시온이와 민우는 베스킨라빈스 게임을 하기로 했지만 이 게임이 너무 유명한 나머지 시온이와 민우 모두 필승 방법을 알고 있었다. 평소에 항상 운이 없던 시온이는 가위바위보를 져 민우에게 선공을 빼았기게 되었고 이대로 게임을 한다면 질 수밖에 없는 상황이다. 그래서 시온이는 1개 이상, N개 이하의 수를 부를 수 있는 규칙의 게임으로 변형하자고 말하였고 민우도 수락했다.

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

입력

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

출력

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

예제 입력

2

예제 출력

1
2

내가 했던 풀이 방법

일반적인 베스킨라빈스 필승법(3개 이하의 수)은 다음과 같다.

이를 토대로 일반화된 필승법은 다음과 같다.

즉, 30%(i+1)의 결과가 0일때 시온이가 이길 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());

        for(int i=1; i<=number; i++) {
            if(30%(i+1)==0) {
                System.out.println(i);
            }
        }
    }
}

회고

베스킨라빈스 필승법을 알고있으면 풀 수 있는 문제였다. 조금 더 시간을 들였다면, 100% 혼자서 해결할 수 있었을 것 같은데 필승법까지만 알아냈고, 그 규칙을 이해하지 못했다는 게 너무 아쉬웠던 문제. 문제 풀이할 때 게임이론 문제가 제일 어려운 것 같다. 필승하는 방법을 나만 못찾겠나 게임이론 관련 문제들을 많이 풀어봐야 할 것 같다.

참고 자료

베스킨라빈스31게임에 숨어있는 수학원리 찾아내기!