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

문제 링크

---

1. 아이디어

각 차례에 1개, $K$개, $K^2$개, …의 금화를 가져갈 수 있을 때, 선공이 이기기 위해 첫 차례에 가져가야 하는 금화 수의 최솟값(이길 수 없으면 0)을 구하는 문제다. $K$가 홀수이면 $K$의 거듭제곱이 모두 홀수라서 한 번 가져갈 때마다 남은 금화의 홀짝이 바뀌므로, 처음 금화가 홀수 개이면 선공이 매번 짝수 개를 넘기며 마지막 금화를 가져가고 짝수 개이면 후공이 이긴다. 선공이 이기는 경우 가장 적게 가져가는 방법은 1개이고, 이길 수 없으면 0을 출력한다.

$K$가 짝수이면 $K + 1$로 나눈 나머지 기준으로 $K$는 -1과 같아서 $K$의 거듭제곱이 1과 -1을 번갈아 나오므로, 어떤 이동이든 금화 수를 $K + 1$로 나눈 나머지가 1씩 바뀐다. 그래서 그런디 수가 $K + 1$ 주기로 반복되며, 나머지가 0부터 $K - 1$까지는 0과 1이 번갈아 나오고 $K$일 때만 2가 된다. 나머지가 $K$이면 1개를 가져가서는 그런디 수가 0인 상태가 되지 않고 $K$개를 가져가야 나머지가 0이 되므로 답은 $K$이다. 나머지가 홀수이면 1개를 가져가 나머지를 짝수로 만들 수 있어 답이 1이고, 나머지가 $K$가 아닌 짝수이면 어떻게 가져가도 이길 수 없어 답이 0이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(T)$	$O(1)$

($T$ = 테스트 케이스 수)

---

3. 코드

풀이 [Java][C++]

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 != 0) {
                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);
    }
}

#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';
            }
        }
    }
}

---