[백준] 15787 기차가 어둠을 헤치고 은하수를

April 27, 2021 ( last updated : April 27, 2021 )
비트마스크 알고리즘

https://github.com/sneakstarberry/

Abstract

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

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

백준 15787번

알고리즘 유형

문제 이해

기차가 통과하는 수!

풀이방법

비트마스크를 응요하여 손쉽게 풀 수 있다.

#include <cstring>
#include <iostream>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int n, m;
  int trains[100000 + 1];
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int code, train_num, seat;
    cin >> code >> train_num;

    if (code == 1) {
      cin >> seat;
      trains[train_num] |= 1 << (seat - 1);
    } else if (code == 2) {
      cin >> seat;
      trains[train_num] &= ((1 << 20) - 1) - (1 << (seat - 1));
    } else if (code == 3) {
      trains[train_num] = (trains[train_num] << 1) & ((1 << 20) - 1);
    } else if (code == 4) {
      trains[train_num] = trains[train_num] >> 1;
    }
  }

  int cnt = 0;
  int passed[1 << 20] = {
      0,
  };
  for (int i = 1; i <= n; i++) {
    if (passed[trains[i]] == 0) {
      passed[trains[i]] = 1;
      cnt++;
    }
  }

  cout << cnt;

  return 0;
}

Originally published April 27, 2021
Latest update April 27, 2021

Related posts :

{# #}