티스토리 뷰

ALGORITHM

백준 / 11723번 / 집합 / C++

chrisysl 2019. 2. 15. 16:01

# 출처 : https://www.acmicpc.net/problem/11723




처음 아이디어는 벡터 구현해서 풀면 되겠지 싶었으나 메모리제한을 고려하면 배열을 이용한 벡터는 구현 해도 문제가 될 것 같았다.

따라서 비트마스크를 사용하여 풀었다. 기본 연산들 가령 and, or, xor 같은것들을 다시한번 떠올려 볼 수 있었다.

이때 remove 에선 and 연산을 사용하여 적절하게 처리할 수 있는데, ~ 를 사용하여 전체 비트를 뒤집고 and 연산을 수행하여

원하는 숫자에 해당하는 비트만 제거할 수 있었다.




# 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
using namespace std;
 
int M, num, BIT;
string input;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> M;
    while (M--)
    {
        input.clear();
        cin >> input;
        if (input == "add")
        {
            cin >> num;
            BIT |= (1 << num);
        }
        else if (input == "remove")
        {
            cin >> num;
            BIT &= ~(1 << num);
        }
        else if (input == "check")
        {
            cin >> num;
            if (BIT & (1 << num))    cout << 1 << '\n';
            else    cout << 0 << '\n';
        }
        else if (input == "toggle")
        {
            cin >> num;
            BIT ^= (1 << num);
        }
        else if (input == "all")
        {
            BIT = (1 << 21- 1;
        }
        else if (input == "empty")
        {
            BIT = 0;
        }
    }
    return 0;
}
cs


댓글
댓글쓰기 폼
공지사항
Total
295,312
Today
8
Yesterday
276
링크
TAG
more
«   2022/09   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
글 보관함