[백준 15787번] 기차가 어둠을 헤치고 은하수를 (C++)

문제링크 : https://www.acmicpc.net/problem/15787

15787번: 기차가 어둠을 헤치고 은하수를

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[100001];

int main() 
{
   ios_base::sync_with_stdio(false); 
   cin.tie(0);
   int n, m; 
   cin >> n >> m;
	while(m--)
   {
 		int command, idx, x; 
      cin >> command >> idx;
		if (command <= 2) cin >> x;
		if (command == 1) arr[idx] |= (1 << x); //1번 연산
		else if (command == 2) arr[idx] &= ~(1 << x); //2번 연산
		else if (command == 3) //3번 연산
      {
			arr[idx] <<= 1; //한칸씩 뒤로
         arr[idx] %= (1<<21); //20번째 값 삭제
		}
		else if (command == 4) //4번 연산
      {
			arr[idx] >>= 1; //한칸씩 앞으로
			arr[idx] &= ~1; //1번째 값 삭제
		}
	}
	set<int>result;
	for (int i = 1; i <= n; i++) 
   {
		result.insert(arr[i]);
	}
	cout << result.size();
   return 0;
}

비트마스킹문제이다.

비트마스킹의 숙련도가 많이 낮은 탓에 고생을 많이 했다.

or 연산을 통해서 추가를 and 연산을 통해서 제거를 하였다.

 

여기서 주의해야할 것이 3번 연산이다.

3번 연산을 할때 한칸씩 뒤로 밀면서 기존의 20칸에서 21칸으로 늘어나게 된다.

이때 우리가 제거할 것은 기존의 20칸이자 현재의 21칸이다.

이를 잘못 제거하면 엉뚱한 값이 제거가 되거나 칸이 계속 추가되는 경우가 발생할 수도 있다.

 

그리고 set 연산을 통해 중복을 걸렀다.

 

이곳저곳 검색해보면서 내가 확실히 이해하고 직관성이 높다고 생각한 것을 가져와 정리한 코드다.

앞으로 비트마스킹 문제를 더 풀면서 참고없이 무난하게 풀 수 있도록 노력해야겠다.