[BOJ/백준] 15787 기차가 어둠을 헤치고 은하수를 파이썬

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

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

비트 연산, 비트마스킹 문제이다.

 

명령 1은 해당 자리 비트를 1로 변경한다

명령 2는 해당 자리 비트를 0으로 변경한다

명령 3은 왼쪽 쉬프트 연산이다

명령 4는 오른쪽 쉬프트 연산이다.

 

주의 할점이 있다.

1. 쉬프트 연산 방향

 - 비트는 오른쪽에서 왼쪽으로 순서이므로 방향에 주의하자.

 

2. 왼쪽 쉬프트 연산

좌석은 최대 20개 이다. 만약 20번째 좌석에 승객이 앉았고 명령 3을 수행하면 20번째 좌석의 승객은 내려야한다.

따라서 0~2^20사이의 숫자만 허용한다. 그러므로 모듈러 연산을 통해 범위를 제한하자.

 

 

from sys import stdin

input = stdin.readline

n,m = map(int, input().split())
orders = []
for _ in range(m):
    order = list(map(int, input().split()))
    if len(order) == 2:
        order.append(-1)
    orders.append(order)
def solv():
    trains = [0]*(n+1)
    for typ, train_num, passenger_num in orders:
        passenger_num -= 1
        if typ == 1:
            trains[train_num] |= (1 << passenger_num)
        elif typ == 2:
            trains[train_num] &= ~(1 << passenger_num)
        elif typ == 3:
            trains[train_num] = trains[train_num] << 1
            if trains[train_num] >= 2**20:
                trains[train_num] %= 2**20
        elif typ == 4:
            trains[train_num] = trains[train_num] >> 1

    answer = 0
    visited = [False]*(2**20)
    for status in trains[1:]:
        if not visited[status]:
            answer += 1
            visited[status] = True

    print(answer)
solv()