백준 11723 - 집합 [C/C++]

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

 

11723번 문제

 

입력과 출력에 관한 설명

 

 개인적으로, 비트마스킹 입문에 아주 최적화된 문제라고 생각한다. 이 문제에서 아주 중요한 점은 비트마스킹을 이 문제에 적용할 수 있는 이유를 빠르게 판단하는 것이다.

 

 우선 비트마스킹에 대해 간단히 개념을 설명 해 보자면, int의 경우 4바이트, 즉 32비트 (4바이트 x 8비트)로 숫자 0과 1의 조합으로 저장되는데, 예를 들어 1은 0000 0000 0000 0000 0000 0000 0000 0001 과 같은 경우로, 8은 0000 0000 0000 0000 0000 0000 0000 1000 으로 저장된다. 이때 이 비트들을 마스킹한다는 것은 0 혹은 1로 값들을 조정한다는 것을 의미한다. (우리의 의도에 따라서)

 

 이 문제에서는 오직 check 명령어인 경우의 출력만을 요구하며, 구체적인 값을 물어보는 것이 아닌 그저 "있는지 없는지"만 물어보고 있다. 이는 값을 저장할 필요가 없다는 뜻이며, 그냥 0과 1, 즉 이분법적으로 나누어 생각해서 코드를 작성해도 문제가 없다는 것이다. 

 

 그러니, check 1인 경우에 첫 번째 비트에 1이 떠있냐? check 15인 경우에 15번째 비트에 1이 떠있냐? 로 치환시켜 다르게 바라 보아도 전혀 문제풀이에 지장이 없다는 뜻이 된다.

 

 따라서 비트를 마스킹하는 방법에 대해서는 추후에 따로 포스팅을 진행하도록 하고, 아래는 필자가 작성한 C++ 코드이다.

 

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

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

    string inst;
    int check, howmany;
    check = 0;

    int s = 0;

    cin >> howmany;
    while(howmany>0){
        howmany--;
        cin >> inst;
        if(inst=="check"){
            cin >> check;
            if (s & (1<<check)){cout << 1 << '\n';}
            else{cout << 0 << '\n';}
        }
        else if (inst == "all"){s |= (1<<32)-1;}
        else if (inst == "empty"){s = 0;}
        else if (inst == "add"){
            cin >> check;
            s |= (1<<check);
        }
        else if (inst == "remove"){
            cin >> check;
            s &= ~(1<<check);
        }
        else if (inst == "toggle"){
            cin >> check;
            if (s & (1<<check)){s &= ~(1<<check);}
            else{s |= (1<<check); }
        }
    }
    return 0;
}

 

 

 시간 초과 예방을 위해 빠른 입출력을 사용하고, 각 명령어가 들어오는 경우에 따라 적절히 비트를 마스킹한다.