[백준/C++] 집합 (No. 11723)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 DP문제를 풀기 전 비트마스킹에 익숙해지라고 나온 문제다.

 

사실 이 전에 N-Queen 문제와, SWEA의 XOR 문제를 풀면서 익숙해졌기 때문에 쉽게 풀 수 있는 문제였다.

 

이 문제에서 숫자가 1~20밖에 없으므로 시프트 연산을 이용해 특정 자릿수에 해당하는 수가 집합에 있는지 없는지 찾으면 된다.

 

이 과정에서 숫자를 추가할 때는 or 연산으로 추가하고 Check를 하는 과정은 and 연산으로 해결했다.

 

예를 들어 2^3과 num이라는 수를 or 연산하면 3번째 자리는 수가 켜지게 된다.

 

또한 2^3과 num이라는 수를 and 연산 하면 이진수로 변환했을 때 num의 2^3이 1일 때만 1이 된다.

 

위와 같은 연산을 통해 집합에 원소가 있는지 없는지 확인하고 출력해 문제를 해결했다.

 

 

 

 

Code

 

 

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

const int DEF = pow(2, 21) - 1;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int tc;
    cin >> tc;
    string str;
    int idx,num=0, bitA;
    for (int t = 0; t < tc; t++) {
        cin >> str;
        if (str == "empty") {
            num = 0;
        }
        else if (str == "all") {
            num = DEF;
        }
        else {
            cin >> idx;
            bitA = 1 << idx;
            if (str == "add") {
                num |= bitA;
            }
            else if (str == "check") {
                if ((num & bitA) == bitA) {
                    cout << "1\n";
                }
                else {
                    cout  << "0\n";
                }
            }
            else if (str == "remove") {
                if ((num&bitA)==bitA){
                    num -= bitA;
                }
            }
            else if (str == "toggle") {
                if ((num & bitA) == bitA) {
                    num -= bitA;
                }
                else{
                    num += bitA;
                }
            }
        }
    }

    return 0;
}

 

---

처음에 입출력 스트림 동기화를 해제하지 않아 시간초과가 났다.

ios::sync_with_stdio를 이용해 입출력 스트림의 동기화를 해제하니 바로 해결할 수 있었다.

 

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