백준 24678: 돌무더기 게임 1

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

24678번: 돌무더기 게임 1

 

풀이를 한 100줄 쓴 거 같은데...

쓰다가 다 지워버렸다.

너무 간단한 풀이가 생각나서

 

출처: 나이브스 아웃: 글래스 어니언

돌무더기가 내 차례에

짝수 짝수 짝수

상태로 놓여있다고 생각해보자

 

그럼 상대편 차례일때는 무조건

홀수 홀수 홀수

일 것이다.

왜냐하면 각 돌무더기에 대해 돌 하나를 가져가거나 올려놓거나 하니까 짝수는 홀수로 홀수는 짝수로 바꾸는 거다.

 

그리고 내 차례엔 무조건

짝수 짝수 짝수

일 것이다.

 

즉, 게임의 진행도와 관계없이 자기 차례에서 짝수 개수와 홀수 개수는 보존된다.

 

이 게임에서 이기려면 돌무더기 상태가 내 차례에

0 0 0 또는 0 0 X 상태여야 하는데 (X는 자연수 아무거나 가능)

0은 짝수라서 상대편 차례일 땐 이 상태가 찾아올 가능성이 전혀 없다.

 

그래서

짝수 짝수 짝수 인 경우엔 내가 이긴다.

 

같은 원리로,

짝수 짝수 홀수 인 경우엔 내가 이기고,

 

홀수 홀수 홀수 또는

홀수 홀수 짝수 인 경우엔 내가 진다.

 

내 차례에 돌 개수가 짝수개인 돌무더기가 3개 이상이면 무조건 내가 이기는 거다.

이 간단한 풀이를 맞았습니다!!를 받은 지 30분 후에야 생각해냈다. 아마 이게 문제 의도였을 거다.

 

다음은 C언어로 구현한 것 ......

int main()
{
    int t, x;
    scanf("%d", &t);
    for (int i = 0;i < t;i++)
    {
        int count = 0;
        for (int j = 0;j < 3;j++)
        {
            scanf("%d", &x);
            if (x % 2 == 1)
                count++;
        }
        if (count > 1)
            printf("B\n");
        else
            printf("R\n");
        
    }
}