https://www.acmicpc.net/problem/15787
문제
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번째 줄까지 각 줄에 명령이 주어진다.
출력
은하수를 건널 수 있는 기차의 수를 출력하시오.
문제 풀이
비트마스킹 문제.
각 자리를 0~19자리까지의 이진법으로 표현해주면 된다. 사람을 태우는 것은 해당 자리가 1인지 0인지 상관없이 1을 추가하면 된다. 따라서 or 연산을 해주면 된다. 사람이 내리는 것은 해당 자리의 현재 값과 상관없이 0으로 만들어야 하므로 and 연산 후 not 연산을 취해주면 된다.
한 칸씩 뒤로 가거나 앞으로 가는 명령은 shift 연산을 수행해주면 된다. 단, 20자리 기차로 고정되어 있으므로 한 칸씩 뒤로 가는 연산인 3번은 현재 19번 자리의 결과가 존재하지 않는 20번 자리로 옮겨가므로, 20번 자리는 사람의 내리는 것과 마찬가지로 해당 자리를 비워주는 연산을 한다.
구현을 1~20번째 자리로 구현했다면 4번 명령도 3번 명령과 마찬가지로 0번 자리를 비워주면 된다.
아래는 코드.
#include <iostream>
#include <set>
using namespace std;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
int N, M;
int trainNum, query, seatNum;
set<long long> s;
cin >> N >> M;
long long* arr = new long long[N+1];
for (int i = 1; i < N+1; i++)
{
arr[i] = 0;
}
for (int i = 0; i < M; i++)
{
cin >> query >> trainNum;
if (query == 1)
{
cin >> seatNum;
arr[trainNum] |= (1LL << (seatNum - 1));
}
else if (query == 2)
{
cin >> seatNum;
arr[trainNum] &= ~(1LL << (seatNum - 1));
}
else if (query == 3)
{
arr[trainNum] = arr[trainNum] << 1;
arr[trainNum] &= ~(1LL << 20);
}
else
{
arr[trainNum] = arr[trainNum] >> 1;
}
}
for (int i = 1; i <= N; i++)
{
s.insert(arr[i]);
}
cout << s.size() << "\n";
return 0;
}