[BOJ / C++] 25592번 : 바둑돌 게임

문제

게임을 좋아하는 푸앙이는 요즘 "바둑돌 게임"이라는 게임을 즐겨한다.

바둑돌 게임은 두 명이 번갈아 가며 한 개의 바둑돌 무더기에서 바둑돌을 정해진 개수만큼 가져가는 게임이다. 처음 시작한 사람은 바둑돌을 1개를 가져가야 하고, 그다음 차례인 사람이 지난 차례에 가져갔던 바둑돌보다 한 개 더 많은 2개를 가져가야 한다. 그다음 차례에는 이전 차례보다 한 개 더 많은 3개를 가져가야 한다. 이런 식으로 차례를 반복해서 자신의 차례에 정해진만큼의 바둑돌을 못 가져간 사람이 게임에서 지게 된다.

게임의 규칙을 완벽하게 이해하고 있던 푸앙이는 같이 바둑돌 게임을 하기로 한 친구를 이기기 위해, 바둑돌 무더기에 바둑돌을 추가하기로 결심했다. 이때, 바둑돌을 너무 많이 추가하면, 친구가 수상해 할 수 있으니, 가능한 한 적은 양의 바둑돌을 추가하기로 했다.

푸앙이가 먼저 게임을 시작한다고 했을 때, 푸앙이가 게임에서 이기기 위해 추가해야 하는 최소한의 바둑돌의 개수를 구해주는 프로그램을 만들어주자. 단, 바둑돌을 추가하지 않아도 된다.

입력

첫 번째 줄에 바둑돌 무더기에 있는 바둑돌의 개수를 의미하는 정수 N$N$ (1≤N≤100000)$(1 \leq N \leq 100\,000)$이 입력된다.

출력

푸앙이가 게임에서 이기기 위해 바둑돌 무더기에 추가해야 할 최소의 바둑돌의 개수를 출력한다.

Solved.ac 레벨

브론즈 IV

풀이

#include <bits/stdc++.h>

using namespace std;

int n, cnt;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    while(n >= cnt){
        n -= cnt;
        cnt++;
    }

    if(cnt % 2 != 0){
        cout << cnt - n << endl;
    } else{
        cout << 0 << endl;
    }

    return 0;
}

푸앙이는 항상 먼저 시작한다는 것을 가정하고 시뮬레이션을 돌려보면 푸앙이는 항상 홀수 개의 돌을 가져가게 되어있다.

다음 차례에 가져가야할 돌의 개수가 홀수이면서 남은 바둑돌이 가져가야할 돌의 개수보다 적다면 그 차를 출력하고

그렇지 않다면 0을 출력하면 되는 쉬운 문제였다.

25592번: 바둑돌 게임