[BaekJoon] 5386번 - 금화 게임 [Java][C++]

문제 링크

---

1. 아이디어

K의 제곱수만큼의 금화를 가져갈 수 있을 때 승리할 수 있는 해적을 구하는 문제로 그런디 수의 규칙성을 통해서 해결했다. 먼저 K가 홀수인 경우 홀수의 제곱수는 모두 홀수이므로 두 해적이 서로 홀수 개의 금화를 가져가게 되고 이는 남은 금화의 홀짝이 계속 바뀌게 된다. 따라서 초기 금화의 개수가 홀수면 선공이 이기며, 짝수면 후공이 이긴다.(후공은 남은 금화를 짝수에서 홀수로 옮기는 것 밖에 못하므로 절대 0을 만들 수 없다.) 선공이 이기는 경우 최소 개수인 1개를 먼저 가져가면 되며, 선공이 이길 수 없으면 0을 출력하면 된다.

K가 짝수인 경우 그런디 수를 구해보면 0, 1, 0, 1, …, 0, 1, 2 이런 패턴이 K + 1 주기로 나타나는 것을 볼 수 있다. S를 K + 1로 나눈 나머지에 해당하는 그런디 수가 2면 금화 K개를 가져가서 그런디 수가 0인 상태로 만드는게 최소 개수를 가져가고 이기는 방법이며,(1개를 가져가면 그런디 수가 0이 아니다.) 나머지에 해당하는 그런디 수가 1이면 1개를 가져가서 그런디 수가 0인 상태로 만드는게 최소 개수다. 그 외의 경우는 이길 수 없다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            if (k % 2 == 1) {
                sb.append(s % 2).append("\n");
            } else {
                if (s % (k + 1) == k) {
                    sb.append(k).append("\n");
                } else {
                    sb.append(s % (k + 1) % 2).append("\n");
                }
            }
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int s, k;
        cin >> s >> k;

        if (k % 2) {
            cout << s % 2 << '\n';
        } else {
            if (s % (k + 1) == k) {
                cout << k << '\n';
            } else {
                cout << s % (k + 1) % 2 << '\n';
            }
        }
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---