문제
N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.
기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다.
기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다.
명령의 종류는 4가지로 다음과 같다.
- 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
- 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
- 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
- 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
M번의 명령 후에 1번째 기차부터 순서대로 한 기차씩 은하수를 건너는데 조건이 있다.
기차는 순서대로 지나가며 기차가 지나갈 때 승객이 앉은 상태를 목록에 기록하며 이미 목록에 존재하는 기록이라면 해당 기차는 은하수를 건널 수 없다.
예를 들면, 다음 그림을 예로 들었을 때, 1번째 기차와 같이 승객이 앉은 상태는 기록되지 않았기 때문에 은하수를 건널 수있다. 2번째 기차와 같은 상태도 기록되지 않았기 때문에 2번째 기차도 은하수를 건널 수 있다. 3번째 기차는 1번째 기차와 승객이 앉은 상태가 같으므로 은하수를 건널 수 없다.
처음에 주어지는 기차에는 아무도 사람이 타지 않는다.
은하수를 건널 수 있는 기차의 수를 출력하시오.
입력
입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다.
출력
은하수를 건널 수 있는 기차의 수를 출력하시오.
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
|
import sys
n, m = map(int, sys.stdin.readline().rstrip().split())
train = [0 for i in range(n)]
# 20좌석 -> 0 ~ 19번째 비트 사용
for i in range(m):
cmd = list(map(int, sys.stdin.readline().rstrip().split()))
if cmd[0] == 1:
train[cmd[1] - 1] |= (1 << (cmd[2] - 1))
# 탑승
# 00..1..00 이랑 or 연산
elif cmd[0] == 2:
train[cmd[1] - 1] &= (~(1 << (cmd[2] - 1)))
# 하차
# 11..0..11 = ~ 00..1..00 이랑 and 연산
elif cmd[0] == 3:
train[cmd[1] - 1] = ((train[cmd[1] - 1]) << 1)
train[cmd[1] - 1] &= ((1 << 20) - 1)
# 한 칸씩 뒤로
# left shift 연산
# 20번째 비트는 쓰면 안되니까 2^20-1 이랑 and 연산 -> 0 ~ 19번째 비트는 그대로 나머지는 0으로
elif cmd[0] == 4:
train[cmd[1] - 1] = ((train[cmd[1] - 1]) >> 1)
# 한 칸씩 앞으로
# right shift 연산
# print(train)
print(len(set(train)))
# 중복없게 set으로 출력
|
cs |
비트 마스크를 활용해서 푸는 문제였다.
기차 한 칸에 총 20개의 좌석이 있기 때문에 20 개의 비트를 이용해서 풀면 될 거라는 생각이 들었다.
탑승하는 경우에 대해서 살펴보면 x 번째 칸에 탑승하기 위해서는 1<<x 와 or 연산을 해주면 된다.
1<<x 는 0..1..0 의 꼴로 표현될텐데 이 숫자와 or 연산을 하면 x 번째 칸을 제외한 나머지 칸은 그대로 있고
x번째 칸은 0이든 1이든 상관없이 1이 들어가게 된다.
하차하는 경우는 ~(1<<x) 와 and 연산을 해주면 된다. ~(1<<x) 는 1<<x 보수로 1..0..1 로 표현되는 수로
이 숫자와 and 연산을 하면 x 번째 칸은 무조건 0으로 바뀌고 나머지 칸은 그래도 있게 된다.
한 칸씩 뒤로 가는 경우에는 left shift 연산을 통해서 해결했다. 주의할 점은 20번째 좌석에 사람이 탑승한 경우에
이 사람을 하차시켜야 한다는 것인데 내 코드에서는 0 ~ 19 번째 비트를 사용하기 때문에 20번째 비트에 기록이 될
것이다. 따라서 1<<20 - 1 (11..11) 과 and 연산을 해서 하차하는 것까지 구현해야 한다.
한 칸씩 앞으로 가는 경우에는 right shift 연산을 해주면 되고 따로 신경쓸 부분은 없었다.
마지막으로 좌석 구성이 중복되면 안 되기 때문에 set을 사용해서 처리해주면 되는 문제였다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 14499 주사위 굴리기 (0) | 2021.03.24 |
---|---|
백준 온라인 저지 12018 Yonsei TOTO (0) | 2021.03.11 |
백준 온라인 저지 20943 카카오톡 (0) | 2021.03.02 |
백준 온라인 저지 20937 떡국 (0) | 2021.03.01 |
백준 온라인 저지 2143 두 배열의 합 (0) | 2021.02.26 |