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

와.. 이름만 보고 풀기로 마음먹었는데

예상외로 비트연산을 이용해야하는 문제라 애 좀 먹었다.. (다 까먹어서.. 멍충)

 

그냥 배열로 순회하면서 구현했을때는 시간초과가 나서, 기억 저편에 있던 비트연산을 다시 공부하며 풀었다.

 

(참고) - https://velog.io/@surpiz/C15787%EB%B2%88-%EA%B8%B0%EC%B0%A8%EA%B0%80-%EC%96%B4%EB%91%A0%EC%9D%84-%ED%97%A4%EC%B9%98%EA%B3%A0

 

챗지피티한테 이것저것 물어보면서 이해했는데 이 똥멍청이가 자꾸 자기가 한말을 번복해서 이해하는데 엄청 오래 걸렸다.. (사실 내가 똥멍청이)

아무튼.. 코드를 작성하며 이해가 잘 안간 비트 연산들을 필기해놓은 것들을 같이 첨부한다. 부디 나처럼 헤매는 분들이 있다면 도움이 되길 바라며..

아 혹시 몰라서 배열로 진행한 코드도 같이 첨부하겠다.

 

 

 

 

 

<비트연산 이용 코드> - 정답

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;
    //0~20까지의 기차 좌석
    vector<int> train(N+1, 0);

    for(int i=0; i<M; i++) {
        int c, j, k; cin >> c;
        switch (c)
        {
        case 1:
            cin >> j >> k;
            //k번째 승객 탑승
            train[j] |= (1 << k);
            break;
        case 2:
            cin >> j >> k;
            //&연산자로 k번째 승객 하차, 나머지 좌석 유지
            train[j] &= ~(1 << k);
            break;
        case 3:
            cin >> j;
            //승객 전체 left shift, 가장 오른쪽(1번째) 0
            train[j] = train[j] << 1;
            // 21번째 좌석이 생길수도 있으므로, 좌석 20개 유지
            train[j] = train[j] & ((1 << 21) - 1);
            break;
        case 4:
            cin >> j;
            //1번째 승객 하차
            train[j] = train[j] & ~1;
            //승객 전체 right shift
            train[j] = train[j] >> 1;
            break;
        default:
            break;
        }  
    }

    //set으로 중복 제거
    set<int> s;
    for(int i=1; i<=N; i++) {
        s.insert(train[i]);
    }

    cout << s.size() << "\n";
    return 0;
}

 

 

<배열 이용 코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<vector<int> > train(N, vector<int>(21,0));
    for(int i=0; i<M; i++) {
        int c, j, k; cin >> c;
        switch (c)
        {
        case 1:
            cin >> j >> k;
            if(j<-0|| j>=N || k<0 || k>=21) continue;
            if(train[j][k]==0) train[j][k] = 1;
            break;
        case 2:
            cin >> j >> k;
            if(j<-0|| j>=N || k<0 || k>=21) continue;
            if(train[j][k]==1) train[j][k] = 0;
            break;
        case 3:
            cin >> j;
            for(int p=19; p>=0; p--) {
                train[j][p+1] = train[j][p];
            }
            train[j][0] = 0;
            break;
        case 4:
            cin >> j;
            for(int p=1; p<21; p++) {
                train[j][p-1] = train[j][p];
            }
            train[j][20] = 0;
            break;
        default:
            break;
        }  
    }

    vector<vector<int> > unique_train;

    for(const vector<int>& v : train) {
        if(find(unique_train.begin(), unique_train.end(), v)== unique_train.end())
            unique_train.push_back(v);
    }

    cout << unique_train.size() << "\n";
    return 0;
}