백준 15787 기차가 어둠을 헤치고 은하수를 (비트마스킹) c++

문제

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

문제해설

N개의 기차가 있고 각 기차에는 20개의 좌석이 있다.
4가지의 명령이 주어지고 명령을 다 수행한 뒤
기차의 승객들이 앉은 형태가 중복된 기차를 제외한 기차의 수를 세면 된다.

문제풀이

그냥 단순하게 배열을 만들어 전부 비교해주면 좋겠지만
기차의 수는 최대 100000개이다.
반복문 한번안에 중복되지 않는 기차를 구해야 되는 것이다.
또한 명령의 개수도 100000이어서
20개의 좌석을 배열로 처리한다면 명령에서부터 시간초과가 날 것이다.

이럴 때 비트마스킹이 필요하다.
비트 마스킹을 이용해 명령을 수행하고
기차와의 비교도 비트마스킹을 이용해야 한다.

1번 명령인 승객 탑승은 OR연산을 이용해
arr[b] |= (1 << c); 이런식으로 표현하면 된다.

2번 명령인 하차는 AND연산을 이용해
arr[b] &= ~(1 << c);로 나타내었다.

3번 명령 뒤로 미는 것은 쉬프트 연산을 사용했다.
arr[b] = arr[b] << 1; 뒤로 밀어주고
arr[b] &= ((1 << 21) - 1); 20자리를 넘어갈 수 있으니 처리를 해준다.

4번 명령 앞으로 당겨지는 것 또한 쉬프트 연산이다.
arr[b] = arr[b] >> 1; 마찬가지로 밀고
arr[b] &= ~1; 1로 되는 경우를 처리해준다.

마지막으로 기차간의 승객 좌석 비교는
1 << 21 자리의 배열을 만들어주고
앞 기차부터 해당 승객 배치에 해당하는 수를 방문처리 해준다.
만약 방문처리가 된 수라면 넘어가고
방문처리가 안된 수라면 결과값을 ++ 해주었다.

전체코드

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m; cin >> n >> m;
	vector<int>arr(n + 1, 0);
	for (int i = 0; i < m; i++) {
 		int a, b, c; cin >> a >> b;
		if (a <= 2)
			cin >> c;
		if (a == 1)
			arr[b] |= (1 << c);
		else if (a == 2)
			arr[b] &= ~(1 << c);
		else if (a == 3) {
			arr[b] = arr[b] << 1;
			arr[b] &= ((1 << 21) - 1);
		}
		else if (a == 4) {
			arr[b] = arr[b] >> 1;
			arr[b] &= ~1;
		}
	}
	vector<bool>vis(1 << 21, false);
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (vis[arr[i]] == false)
			res++;
		vis[arr[i]] = true;
	}
	cout << res;
	return 0;
}