반응형
https://www.acmicpc.net/problem/11723
11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
이 문제는 비트 연산 이용하는 문제로 나는 처음에 벡터를 이용해 풀어서 시간초과가 났다.
비트연산을 모르는 사람이 있다면 https://hagisilecoding.tistory.com/54 여기서 공부를 하고 오면 쉽게 이해할 수 있다.
단계별 문제 풀이
1. |= (1<<n) 로 원하는 원소 더해주고
2. &= ~(1<<n) 을 이용하여 원소 제거
3. if(s&(1<<n)) 를 이용해서 check 구현
4. s ^= (1<<n) 를 이용해서 toggle 구현
5. s = (1<<21) - 1 을 이용해서 all 구현
6. s = 0 -> 공집합
전체코드
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
|
#include <iostream>
#include <string>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
unsigned int s = 0;
int m, n;
string a ="";
cin >> m;
while(m--){
cin >> a;
if(a=="add"){
cin >> n;
s |= (1 << n);
}else if(a == "remove"){
cin >> n;
s &= ~(1 << n);
}else if(a== "check"){
cin >> n;
if(s & (1<<n)){
cout << 1 << '\n';
}else{
cout << 0 << '\n';
}
}else if(a=="toggle"){
cin >> n;
s ^= (1<<n);
}else if(a=="all"){
s = (1 << 21) - 1;
}else if(a == "empty"){
s = 0;
}
}
return 0;
} //비트연산자 공부 후 16min
|
cs |
체감 난이도 | 걸린시간 | 참고 | 사용 알고리즘, 문법 |
중 | 16min | 비트 마스킹을 이용해야한다는 힌트를 보고 비트 마스킹을 해본적이 없어 비트 마스킹에 대해 공부 품 |
비트 마스킹 |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 1780 종이의 개수 c++ [컴공과고씨] (0) | 2022.04.03 |
---|---|
백준 1676 팩토리얼 0의 개수 c++ [컴공과고씨] (0) | 2022.04.03 |
백준 스터디 기록장 (0) | 2022.04.02 |
백준 18870 좌표압축 c++ [컴공과고씨] (0) | 2022.04.02 |
백준 1764 듣보잡 c++ [컴공과고씨] (1) | 2022.04.01 |