[백준] 1322번_X와 K C++

20 Apr 2023 in Study on Coding Test

비트마스킹을 사용하는 문제

정답제출코드

#include <iostream>

using namespace std;

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

    long long X, Y, K;
    long long ZeroCount = 0;

    cin >> X >> K;
    
    long long I = 0;
    while(true)
    {
        if (!(X & ((long long)1 << I)))
        {
            ZeroCount++;
            if(((long long)1 << ZeroCount)-1 >= K)
                break;
        }
        I++;
    }

    Y = 0;
    while(I >= 0 && ZeroCount > 0 && K > 0)
    {
        if (!(X & ((long long)1 << I)))
        {
            if ((long long)1 << (ZeroCount-1) <= K)
            {
                Y |= ((long long)1 << I);
                K = K - ((long long)1 << (ZeroCount-1));
            }
            --ZeroCount;
        }
        --I;
    }

    cout << Y;

    return 0;
}

이번 문제를 비트마스킹이라는 감이 왔지만,

비트마스킹은 연습을 별로 안해봤던 분야라서 어려웠던 것 같다.

    cin >> X;
    cin >> K;

    while (K)
    {
        if ((X | Y) == (X + Y))
            K--;
        Y++;
    }
    ans = X + Y;

처음에 내가 생각했던 코드.

X	Y 연산 자체는 C++로 지원하기 때문에 쉽게할 수는 있는데

문제는 이것을 어떻게 빨리하느냐이다.

입력 값, 계산 값의 최대치가 20억이기 때문에 일일이 하나씩 하면 오래걸린다.

그래서 규칙을 찾을 필요가 있었지만 솔직히 못찾아서 구글링을 했다.

참고링크에 따르면, 규칙은 아래와 같다고 한다.

• X와 Y의 비트에서 1이 서로 겹치게 등장하면 안된다.
• X의 비트 값이 0인 부분에만 K의 2진수 표현을 집어넣으면 된다.

예를 들어, X가 101001이고, K가 5일 경우 만족하는 Y는

• X : 101001
• K : 010010
• Y : 111011

이다.

이런 부분을 구현해주면 되는 것이었다!

그래서 작성한 정답코드는 위와 같다.

C++을 쓰고 있음에도 불구하고 비트연산은 익숙치가 않다. 이부분 많이 연습해야겠다.