[실전 문제] 구슬 게임

1. 문제

철수와 영희는 구슬 게임이 구슬 게임을 하려 한다. 이 구슬 게임의 규칙은 다음과 같다.

1. 철수와 영희는 번갈아가며 구슬을 가져간다. 맨 처음에는 철수가 구슬을 가져간다.
2. 구슬을 가져갈 때에는, 최소 1개에서 최대 3개까지 구슬을 가져갈 수 있다.
3. 가져갈 구슬이 없는 사람이 진다.

예를 들어 5개의 구슬이 있다고 하자. 여기서 철수가 1개의 구슬을 가져가고, 영희가 3개의 구슬을 가져간 후, 철수가 마지막으로 1개의 구슬을 가져갔다고 가정하면 이 게임의 승자는 철수가 된다. 물론, 각자가 어떻게 구슬을 가져가느냐에 따라 승패가 달라질 수 있다. 철수와 영희는 이기기 위해서 최선을 다해서 게임을 플레이 한다. n개의 구슬을 시작으로 게임을 진행한다고 할 때, 철수가 이 게임을 이길 수 있다면 YES, 그렇지 않다면 NO를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 전체 구슬의 개수n 이 주어진다. (0 ≤ n ≤ 1,000,000) 

출력

첫째 줄에 철수가 이길 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

예제 입력

case 1) 3

case 2) 5

case 3) 191124

예제 출력

case 1) YES

case 2) YES

case 3) NO

 

 

 

2. 풀이

이 풀이에서 가장 핵심은 철수와 영희가 서로 이기기 위해서 최선을 다한다는 점이다. 즉, 영희차례에서 영희도 철수를 이기고자 하다는 뜻이다. 이 점을 주의하여 나열하면 다음과 같다.

구슬	철수	영희	철수가 이길 가능성
1	O		O
2	OO		O
3	OOO		O
4	case 1) OOO case 2) OO case 3) O	case 1) O case 2) OO case 3) OOO	X (모든 케이스 불가능)
5	case 1) OOO case 2) OO case 3) O / O	case 1) OO case 2) OOO case 3) OOO	O (3번 케이스 가능)
6	case 1) OOO case 2) OO / O	case 1) OOO case 2) OOO	O (2번 케이스 가능)
7	case 1) OOO / O	case 1) OOO	O (1번 케이스 가능)
8	case 1) OOO / OOO case 2) OO / OOO case 3) O / OOO	case 1) O / O case 2) O / OO case 3) OOO / OO	X (모든 케이스 불가능)

이를 통해 할 수 있는 것은 4의 배수마다 영희가 이기는 것을 알 수 있다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int n = Integer.parseInt(br.readLine());
        
        if(n % 4 == 0) bw.write("NO\n");
        else bw.write("YES\n");

        br.close();
        bw.flush();
        bw.close();
    }

}