[BAEKJOON] 백준 25592: 바둑돌 게임 (C#)

문제 링크

https://www.acmicpc.net/problem/25592

 

 

문제

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

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

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

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

 

 

입력

첫 번째 줄에 바둑돌 무더기에 있는 바둑돌의 개수를 의미하는 정수 𝑁 (1≤𝑁≤100000)이 입력된다.

 

 

출력

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

 

 

 

통과한 답안

namespace _25592
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long stones = 0;
            int addStones = 0;

            while (stones <= N)
            {
                addStones++;
                stones += addStones;
            }

            Console.WriteLine(addStones % 2 == 0 ? 0 : stones - N);
        }
    }
}

 

두 명이서 자기 차례만큼 바둑돌을 가져가는 게임을 하는 경우에,

자신이 먼저 바둑돌을 가져가고, 바둑돌의 전체 수를 알고 있을 때,

항상 이기기 위해서 추가로 필요한 바둑돌의 수를 구하는 문제이다.

 

가져가는 바둑돌의 수를 계산해보면

1개, 2개, 3개, 4개, ... , i개 씩 가져가므로

총 바둑돌은 1개, 3개, 6개, 10개, ... (i * (i + 1) / 2)개가 된다.

또, 내가 가져가는 순서는 홀수번째이므로

짝수번째에 부족하면 바둑돌은 필요없고,

홀수번째에 부족하면 그 부족분만큼 추가하면 된다.

 

따라서 전체 돌 수와 추가하는 돌 수를 계산하면서 더해서

N과 같아지거나 커지는 순간을 계산하고,

그 순간이 짝수번째인지 홀수번째인지 확인하고

홀수번째라면 전체 돌과 N의 차이를 추가하면 된다.