[백준 11723] 집합

이 문제는 메모리제한이 4MB이며 대부분 이렇게 메모리제한이 작은 문제는 비트마스킹을 이용해야 한다.

 

x의 범위가 1 ~ 20이므로 32비트 int형 정수 하나로 집합을 표현할 수 있다.

 

1 ~ 20을 각각 1번째비트 ...  20번째 비트로 생각하면 shift 연산으로 i번째 값을 컨트롤 할 수 있다.

 

add는 or연산으로 1 | 0 = 1, 1 | 1 = 1이니 add를 몇 번 하더라도 해당 비트는 항상 1이게 된다

 

remove는 i번째 비트를 꺼야하니 1011같이 해당 비트를 0으로 만들어야 하는데 이는

0100으로 shift를 하고 not연산으로 뒤집으면 1011이 된다. and연산은 두 값이 1일때만 1이므로 i번째 값만 꺼지고 나머지 값은 그대로 남아있게 된다

 

check는 현재 값과 i번째 shift한 값을 and연산을 통해 1인지 0인지 판단하면 된다.

 

toggle연산은 1이면 0, 0이면 1로 바꾸는 연산이므로 xor을 이용한다.

 

all연산은 모든 비트를 키는 연산으로 010000이라는 값에 1을 빼면 001111이 되는 것을 통해 1 << 21에 1을 빼서 20개의 모든 비트가 1로 활성화되는 것을 표현 할 수 있다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int M;
    cin >> M;
    int bits = 0;
    while(M-->0) {
        string command;
        cin >> command;
        if(command == "add") {
            int i; cin >> i;
            bits |= (1 << i);
        } else if(command == "remove") {
            int i; cin >> i;
            bits &= ~(1 << i);
        } else if(command == "check") {
            int i; cin >> i;
            cout << ((bits & 1 << i) ? 1 : 0) << '\n';
        } else if(command == "toggle") {
            int i; cin >> i;
            bits ^= (1 << i);
        } else if(command == "all") {
            bits = (1 << 21) - 1;
        } else {
            bits ^= bits;
        }
    }
}