백준 11723번 집합

< 백준 11723번 집합 - 마포 코딩박 >

사용한 알고리즘: 비트마스킹


 비트마스킹을 이용해 문제에서 요구하는 연산을 하는 문제였습니다.

문제풀이는 다음과 같습니다.
(1) (코드 14~18)
 add : 비트 연산자 | (or) 을 사용해줍니다.

(2) (코드 19~23)
 -1 = 111...11 로 저장됩니다. -1 + 1 = 1000....00 = 0 으로 계산되죠! 이를 이용하면 -1-(1<<x) = 111...11 - (1<<x) = 111....101111 로 x번째가 0 이 됩니다.
 따라서 remove : val&(-1-(1<<x)) 를 하게되면 x번째가 0 이 됩니다.

(3) (코드 24~42)
 check 연산은 & (and) 연산자로, toggle 연산은 ^ (xor) 연산자로 해주면 됩니다.
 all 연산은 위에 말한대로 -1 = 111...11 이므로 이를 활용해줍니다.

	#include <iostream>
	#include <string>
	using namespace std;
	int N, x;
	int val;
	string sss;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	cin >> sss;
	if(sss == "add"){
	cin >> x;
	// 1<<x 추가
	val|=(1<<x);
	}
	else if(sss == "remove"){
	cin >> x;
	// -1 = 1111111111... 이고 거기에 1<<x 를 빼면 111111...011111 입니다.
	val&=(-1-(1<<x));
	}
	else if(sss == "check"){
	cin >> x;
	int temp = val;
	// 1<<x 가 있는지 없는지
	if(temp&(1<<x))
	cout << 1 << '\n';
	else
	cout << 0 << '\n';
	}
	else if(sss == "toggle"){
	cin >> x;
	// XOR 의 기능
	val^=(1<<x);
	}
	// -1 = 111111... 이다
	else if(sss == "all")
	val = -1;
	else
	val = 0;
	}
	return 0;
	}

view raw BOJ 11723.cpp hosted with ❤ by GitHub