[SWEA/C++] 돌 추가 게임 (No. 20945)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 풀기 위해서 고민을 좀 많이 했다.

 

문제에 대해 간단히 설명하자면 Nim 게임이라 불리는 문제에서 응용된 문제다.

 

여기서 스프라그-그런디 정리를 Nim 게임에 적용하면 돌 무더기에 대해 xor을 계산하는 것으로 누가 이기는지 알 수 있다.

 

그러므로 후공인 지혜가 이기기 때문에 모든 돌 무더기를 xor값이 0이 되도록 만들기 위해 돌 무더기에 돌을 추가하는데, 이 때 추가해야하는 가장 적은 돌의 양을 계산하면 되는 문제다.

 

그렇다면 돌을 어떻게 추가해야 가장 적게 돌을 추가할 수 있을까?

 

먼저 생각해보면 xor한 값이 주어졌을 때, 1이 나타난 가장 높은 차수에 해당하는 xor값을 0으로 만들어야 한다.

 

이 때, 가장 높은 차수의 1을 0으로 만드는 방법을 생각해보면 크게 2가지로 나눌 수 있다.

 

가장 높은 차수를 n라고 하면

 

1. 특정 돌무더기의 n차수 0을 1로 바꾼다. (0이 존재할 경우)

2. 특정 돌무더기의 n차수 1을 0으로 바꾼다. (1은 반드시 존재)

 

먼저 1번 경우에 대해 그림을 보며 이해해보자.

위 경우를 보면 2^4가 가장 1이 등장하는 차수 중 가장 큰 차수다.   

 

여기서 2번의 0을 1로 바꾼다고 생각해보자.

이때, 2^4개의 돌을 추가해 0을 1로 바꾸면 안된다.

 

왜냐하면 위 그림처럼 4개를 더해 4번째 의 0을 1로 바꿀 수 있기 때문이다.

 

그렇다면, 여기서 n번째의 0을 1로 바꿀 때, 왜 2^n을 더하지 않는게 더 좋은 방법인지 생각해보자.

 

당연하게도 모든 n진법으로 나타낸 숫자는 자리수가 더 큰 수가 크다.

(100이 011, 010, 001 보다 큰게 당연한 것과 같다.)

 

이제 임의의 수 a를 2진법으로 표현했을 때, n번째 자리가 0이라고 가정하자.

 

이때, 임의의 수의 n번째 자리를 1로 바꾸기 위해서는 2^n - a%(2^n)이 가장 적은 돌을 이용해 n번째 자리를 1로 바꾸는 방법이다.  

 

ex) 101001 에서 맨 왼쪽의 0을 1로 바꾸기 위해서는 2^4 - a%(2^4)를 더하면 된다. a = 41이므로 16 - 9 = 7 이다.

 

이를 이용하면 특정 자리수 n이 1일 경우 이 1을 0으로 바꾸는 최선의 경우를 구할 수 있다.

 

모든 수 a_i에 대해 n번째 자리가 0이면서 2^n - a_i%(2^n)의 값이 최소를 찾는다.

 

추가해야할 돌의 수 b = 2^n - a_i%(2^n)

 

이후 최소 추가량 b를 구했다면, b를 그 돌무더기에 더하면 된다. 

 

이제 n번째 자리가 0인 경우에 어떻게 돌을 추가해야하는 지 알아봤다.

 

위 내용에는 왜 b값이 가장 적은 경우를 찾아야 하는지에 대한 이유가 생략되어 있지만, 간단하게 설명하면

10111, 10110의 돌 무더기에서 10111에 돌을 1개 추가하면 11000이 된다.

그러면 남은 돌무더기는 11000, 10110이 된다.

만약 10110에 돌을 2개 추가해 11000을 만들면 남은 돌무더기는 11000, 10111이 된다.

 

이제 두 경우에 대한 차이가 보일 것이다.

돌을 한 개 추가한 [11000, 10110]과 돌을 두 개 추가한 [11000, 10111]을 비교하면 앞의 경우가 최적의 경우를 고려할 수 있다.

왜냐하면 [11000, 10110]에 돌을 하나 추가하면 [11000, 10111]의 경우를 고려할 수 있기 때문이다.

쉽게 생각하면 최적의 경우를 생략하지 않기 위해 가장 적은 돌을 추가해 나가는 방법이다.

 

이제 2번 경우 1을 0으로 바꾸는 경우에 대해 생각해보자.

 

1을 0으로 바꾸는 경우를 고려해야 하는 이유는 간단하다.

 

 

아래와 같은 경우가 생길 수 있기 때문이다.

 

 

n번째 자리의 수를 변경해야하는 데 모든 수가 1이라면 다른 수의 1을 0으로 바꿔야 한다.

 

여기서 우리는 돌무더기에 돌을 추가하기만 가능하기 때문에 돌무더기에 돌을 더해 1을 0으로 바꾼다.

그러면 이 경우에 최적의 방법은 n의 자리수를 1 늘려탐색하는 것이다.

 

그러면 이전에 0을 1로 바꾼 방법을 똑같이 적용해 n+1번째 자리를 1로 바꾸는 가장 작은 수 b를 찾고 b를 더해 돌무더기의 n번째 자리를 0으로 바꿀 수 있다.

 

(위 그림이 이러한 방법을 적용한 경우다.)

 

이제 2가지 경우를 다 고려했다.

 

이제 마지막으로 고려해야하는 경우가 하나 더 있다.

 

예를 들어 7,1,7의 돌무더가기 있을 경우를 생각해보자. 

 

이 경우에 이전의 방법을 따라가다보면 7, 1, 7의 돌무더기에 돌을 15개 추가하게 된다.

 

하지만 실제로 최적의 방법은 아래의 방법이다.

 

즉, 돌무더기에서 가장 많은 돌 무더기의 자리수를 1 늘리는게 가장 좋은 방법일 수 있다는 것이다. 

 

그러므로 위 경우를 고려해 특정 돌무더기의 자리수를 1 늘린 후 이전의 방법을 따라 돌무더기에 돌을 얼마나 추가할지 계산해 비교해야한다.

 

그러면 최종적으로 돌무더기의 자리수를 1 늘린경우와 자리수를 늘리지 않은 경우를 비교해 더 적은 돌을 추가하는 경우를 출력하면 된다. 

 

 

​

[아이디어 정리]

1. xor한 후 1이 가장 먼저 나타나는 n번째 자리를 찾는다.
2. n번째 자리를 찾았다면 n번째 자리가 0인 돌 무더기 중 가장 적은 돌 b를 추가해 n번째 자리의 0을 1로 바꿀 수 있는지 찾는다.
3. b와 돌무더기를 찾았다면, 그 돌무더기에 b만큼 돌을 추가한다.
4. 만약 n번째 자리가 0인 돌무더기가 없다면, n을 1 늘리고 n+1번째 자리가 0인 돌 무더기를 찾아 2번 방법을 적용한다.
5. 위 과정을 반복하며 xor값이 0이 될 때 까지 추가해야하는 돌의 양을 계산한다.
6. 돌을 더 추가해 자리수를 늘리는게 최적인 방법도 있으므로 돌을 추가해 자리수를 늘린 후 1 ~ 5 과정을 반복해 추가해야하는 돌의 양을 한번 더 계산한다.
7. 추가해야하는 돌의 양을 각각 구했다면, 둘 중 더 적은 양이 정답이 된다.

 

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const long long INF = 1987654321;
void ChangeToBi(vector<long long>& v, long long nowN) {
    long long idx = 0;
    for (int i = 0; i < v.size(); i++) {
        v[i] = 0;
    }
    while (nowN > 0) {
        v[idx] = nowN % 2;
        nowN /= 2;
        idx++;
    }
}

int Calc(vector<vector<long long>> V, vector<long long> nim, vector<long long> stone, long long xx) {
    long long ans = 0;
    long long tmp, ppp, plusStone, stoneN;
    bool flag;
    while (true) {
        flag = true;
        int idx = 0;
        for (int i = nim.size() - 1; i >= 0; i--) {
            if (nim[i] == 1) {
                idx = i;
                flag = false;
                break;
            }
        }
        if (!flag) {
            tmp = INF;
            ppp = pow(2, idx);
            stoneN = -1;
            while (stoneN == -1) {
                for (int i = 0; i < V.size(); i++) {
                    if (V[i][idx] == 0) {
                        //plusStone = 
                        /*for (int j = idx - 1; j >= 0; j--) {

                        }*/
                        plusStone = ppp - (stone[i] % ppp);
                        if (plusStone < tmp) {
                            stoneN = i;
                            tmp = plusStone;
                        }
                    }
                }
                idx += 1;
            }

            xx ^= stone[stoneN];
            stone[stoneN] += tmp;
            ans += tmp;
            ChangeToBi(V[stoneN], stone[stoneN]);
            xx ^= stone[stoneN];
            ChangeToBi(nim, xx);
        }
        else {
            return ans;
        }
    }
}

int Bik(int num) {
    int idx = 0;
    while (num > 0) {
        num /= 2;
        idx++;
    }
    return idx;
}


int main() {
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        int N;
        cin >> N;
        vector<long long> stone(N);
        for (int i = 0; i < N; i++) {
            cin >> stone[i];
        }
        vector<vector<long long>> V(N, vector<long long>(32, 0));
        vector<long long> nim(32, 0);
        long long xx = stone[0];
        ChangeToBi(V[0], stone[0]);
        int bigN = Bik(stone[0]);
        int bigStone = 0, bigStoneIdx=0;
        for (int i = 1; i < N; i++) {
            xx ^= stone[i];
            ChangeToBi(V[i], stone[i]);
            bigN = max(bigN, Bik(stone[i]));
            if (stone[i] > bigStone) {
                bigStone = stone[i];
                bigStoneIdx = i;
            }
        }
        ChangeToBi(nim, xx);


        long long dap = Calc(V, nim, stone, xx);
        long long maxN = pow(2, bigN);
        long long pTmp = maxN - stone[bigStoneIdx];
        xx ^= stone[bigStoneIdx];
        stone[bigStoneIdx] = maxN;
        ChangeToBi(V[bigStoneIdx], maxN);
        xx ^= maxN;
        ChangeToBi(nim, xx);
        long long dap2 = Calc(V, nim, stone, xx)+pTmp;
        
        cout << "#" << t << " " << min(dap, dap2) << endl;
    }

    return 0;
}

 

---

문제를 푼 방법을 보면 간단해 보이지만, 실제로 많이 오래 걸린 문제다.

특히 왜 이러한 방법이 최적인지 증명하기가 까다로웠다.

 

n번째 자리를 바꾸는 방법은 빠르게 찾았지만, 자리수를 늘리는 경우가 최적인 경우를 바로 생각하지 못했기 때문이다.

거의 2시간 가량 고민한 끝에 7,1,7과 같은 반례를 찾아 해결할 수 있었다;;

D8이라 그런가 생각할 게 많고 재밌던 것 같기도...

 

SW Expert Academy