백준 15787 백준 기차가 어둠을 헤치고

https://www.acmicpc.net/problem/15787

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

#include <iostream>
#include <vector>
#include <set>

using namespace std;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n, m;
    cin >> n >> m;
    vector<int> arr(n + 1, 0);      //i번째 기차의 탑승 현황

    for (int cmd = 0; cmd < m; cmd++) {
        int opt, i, x; cin >> opt >> i;
        if (opt <= 2)
            cin >> x;

        switch (opt) {
            //기차 i의 x번 좌석의 사람을 승차하는 작업
            case 1:
                arr[i] |= (1 << x);
                break;

            //기차 i의 x번 좌석의 사람이 하차하는 작업
            case 2:
                arr[i] &= ~(1 << x);
                break;

            //해당 열차의 승객이 뒤로 한 칸씩 이동
            case 3:
                arr[i] = arr[i] << 1;
                arr[i] &= (1 << 21);
                break;

            //해당 열차의 승객이 앞으로 한 칸씩 이동
            case 4:
                arr[i] = arr[i] >> 1;
                arr[i] &= ~1;
                break;
        }


    }


    set<int> s;
    for (int i = 1; i <= n; i++) {
        s.insert(arr[i]);
    }

    cout << s.size();
    return 0;
}

 

비트마스킹을 이용해 구현해야 하는 문제이다. 처음에는 벡터를 이용해 구현하려 했으나 1초의 제한시간이 있으므로 시간 초과가 난다. 각 옵션에 대해 다음과 같이 구현해야 한다.

 

1. 1을 x만큼 left shift하면 1000...0이 된다. 여기서 현재 열차와 or연산을 하면 0인 부분은 원래 열차의 현황을 유지(0|k=k)하고 x자리만 1로 치환된다.

2. 1을 x만큼 left shift한 결과를 not 연산을 하면 0111...1이 된다. 이를 and연산 하면 1인 부분은 원래 열차의 현황을 유지하고(1&k=k) x자리만 0으로 치환된다.

3. 해당 열차를 한 칸 left shift하면 높은 자리로 한 칸 이동하기 때문에 1번 자리는 0이 되고, 20번 자리였던 승객은 21번 위치로 가게 된다. 이후 1을 21번 left shift하고 not연산을 하면 21번 자리만 0, 나머지는 1이 되고, 현재 기차와 and연산을 하면 21번 자리는 0이 되어 20번 자리였던 승객은 완전히 하차하게 된다.

3. 해당 열차를 한 칸 right shift하면 낮은 자리로 한 칸 이동하기 때문에 20번 자리는 0이 되고, 1번 자리였던 승객은 0번 위치로 가게 된다. 이후 not 1을 현재 기차와 and연산을 하면 0번 자리를 0으로 만들 수 있다.

 

이후 연산한 결과를 set에 넣는다. set은 중복을 허용하지 않으므로 이 크기를 구하면 정답을 출력할 수 있다.