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

코드

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline

'''
1 i x: i번째 기차의 x번째 좌석에 사람 태우기
2 i x: i번째 기차의 x번째 좌석의 사람 하차
3 i: i번째 기차에 앉아있는 승객들 모두 한칸씩 뒤로
4 i: i번째 기차에 앉아있는 승객들 모두 한칸씩 앞으로 
'''

n, m = map(int, input().split())
train = [0 for _ in range(n)]

for _ in range(m):
    cmd = list(map(int, input().rstrip().split()))
    if cmd[0] == 1:
        train[cmd[1] - 1] |= (1 << (cmd[2] - 1))
    elif cmd[0] == 2:
        train[cmd[1] - 1] &= ~(1 << (cmd[2] - 1))
    elif cmd[0] == 3:
        train[cmd[1] - 1] <<= 1
        train[cmd[1] - 1] &= ~(1 << 20) # 자리수 맞춤
    elif cmd[0] == 4:
        train[cmd[1] - 1] >>= 1


print(len(set(train)))

풀이

처음에 deque로 rotate시켜서 풀어볼까 하다가 비트마스킹에 대한 개념 정리도 할 겸 비트마스킹에 대해 찾아보면서 풀었다.

주의할 점은 뒤쪽으로 한 칸씩 옮길 경우 비트 연산을 하게되면 21칸이 되어버리기 때문에 자리수를 맞춰주어야 한다!

비트 연산 정리

• AND 연산 &
  • 대응하는 두 비트가 모두 1일 때 1 반환

1111 & 1100 = 1100

• OR 연산 |
  • 대응하는 두 비트가 하나라도 1일 때 1 반환

1111 | 1010 = 1111 

• XOR 연산 ^
  • 대응하는 두 비트가 서로 다를 때 1 반환

1000 ^ 1111 = 0111

• NOT 연산 ~
  • 각각의 비트 값을 반전하여 반환

~1111 = 0000

• 왼쪽, 오른쪽 shift
  • 왼쪽 shift « : 왼쪽으로 비트를 밀어준다.
    • A « B: A * 2^B
  • 오른쪽 shift »: 오른쪽으로 비트를 밀어준다.
    • A » B: A / 2^B

10101 << 1 = 101010 -> 한 킨씩 왼쪽으로 밀고 새로운 0이 생긴다
10101 >> 1 = 1010 -> 한 칸씩 오른쪽으로 밀고 맨 오른쪽 비트는 사라진다 

응용

• 원소 삽입
  • 예를 들어 i 번째 자리를 채우고 싶은 경우

x = x | (1 << i)	# i번째 비트가 1인 아이를 만든 후 OR 연산

• 원소 삭제
  • 예를 들어 i 번째 자리를 삭제하고 싶은 경우

x = x & ~(1 << i)	# i 번째 비트가 0인 아이를 만든 후 AND 연산

• 원소 토글
  • 특정 값 p가 있으면 삭제 없으면 추가

x = x ^ (1 << p)

• 원소 비우기 및 채우기

x = 0	# 비우기
x = (1 << 21) - 1	# 20자리가 꽉찬 비트 만들기

참고 사이트

• yuki.log