[BOJ] 15787 기차가 어둠을 헤치고 은하수를

문제

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

N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다.

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

풀이

• 사람 탑승
1 << 위치 해주어 | 연산을 이용한다.

• 사람 하차
1 << 위치를 ~해주어 & 연산을 이용한다.

• 한칸씩 뒤로
arr[기차위치] << 1을 해준 후 맨 뒤칸을 처리해야 한다. 이는 (1 << 20) -1과 & 연산을 하였다.
((1 << 20) - 1이 결국 01111…111이기 때문)

• 한칸씩 앞으로
arr[기차위치] >> 1을 해준다.

코드

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <set>
using namespace std;
 
int n, m;
int ans = 0;
int a, b, c;
deque<int> dq[100000];
set<string> st;
 
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 20; j++) {
            dq[i].push_back(0);
        }
    }
    while (m--) {
        scanf("%d", &a);
        if (a == 3 or a == 4) scanf("%d", &b);
        else scanf("%d %d", &b, &c), c--;
        b--;
        if (a == 1) { // 사람 탑승
            dq[b][c] = 1;
        } else if (a == 2) { // 사람 하차
            dq[b][c] = 0;
        } else if (a == 3) { // 모두 한칸씩 뒤로 밀려남, dq.pop_back, dq.push_front
            dq[b].pop_back();
            dq[b].push_front(0);
        } else { // 모두 한칸씩 앞으로 앞으로 감, dq.push_back, dq.pop_front
            dq[b].push_back(0);
            dq[b].pop_front();
        }
    }
    for(int i = 0; i < n; i++) {
        string s = "";
        for(int j = 0; j < 20; j++) {
            s += char(dq[i][j] + '0');
        }
        if (st.find(s) == st.end()) st.insert(s), ans++;
    }
    printf("%d", ans);
}

#include <cstdio>
using namespace std;
 
int n, m;
int ans = 0;
int a, b, c;
int mask = (1 << 20) - 1;
int arr[100000];
int vis[1<<20];
 
int main() {
    scanf("%d %d", &n, &m);
    while (m--) {
        scanf("%d", &a);
        if (a == 3 or a == 4) scanf("%d", &b);
        else scanf("%d %d", &b, &c), c--;
        b--;
        if (a == 1) {
            arr[b] |= 1 << c;
        } else if (a == 2) {
            arr[b] &= ~(1 << c);
        } else if (a == 3) {
            arr[b] = (arr[b] << 1) & mask;
        } else {
            arr[b] >>= 1;
        }
    }
    for(int i = 0; i < n; i++) {
        if (vis[arr[i]]) continue;
        vis[arr[i]] = 1;
        ans++;
    }
    printf("%d", ans);
}