[백준/C++] 알고리즘 15787번 - 기차가 어둠을 헤치고 은하수를

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 15787번 - 기차가 어둠을 헤치고 은하수를 풀어보도록 하겠습니다.

 

 

 

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

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

 

[문제 접근]

좌석을 비트로 표현하면 각 기차별로의 승객의 좌석현황을 하나의 정수로 표현이 가능하다고 생각했습니다. 그리고 이를 이용하여 기존에 승객좌석현황과 같은 기차가 존재하는지 여부를 판단가능하다고 생각했습니다. 그래서 비트마스킹과 해쉬맵을 이용했습니다.

 

[풀이 전략]

1. 명령번호에 따른 분기처리를 해줍니다.

2. 승객의 좌석을 비트마스킹을 이용하여 정수로 표현한 후 arr에 저장합니다.

3. 기차를 순차적으로 돌면서 해시맵에 승객을 정수로 표현한 값이 있으면 건너뛰고 없으면 1을 저장하고 answer를 1 증가시킵니다.

 

[코드]

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


int n,m ; 

long long arr[100'001];

unordered_map<long long,int> ma;

int answer ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> m ;

    for(int i = 0 ; i < m ; i++){
        int order ;
        cin >> order ;

        if(order == 1) {
            int idx,x ;
            cin >> idx >> x ;
            if(arr[idx] & (1LL << (x-1))) continue; 
            arr[idx] += (1LL<<(x-1));
        }
        else if(order == 2){
            int idx,x ;
            cin >> idx >> x ;
            if((arr[idx] & (1LL << (x-1))) == 0) continue; 
            arr[idx] -= (1LL<<(x-1));
        }
        else if(order == 3){
            int idx;
            cin >> idx ; 
            arr[idx] = (arr[idx] << 1) ;
            arr[idx] = (arr[idx] & ((1LL << 20)-1)); 
        }
        else if(order == 4) {
            int idx;
            cin >> idx ;
            arr[idx] = (arr[idx] >> 1) ;
        }
    }

    for(int j = 1 ; j <= n ; j++){
            if(ma[arr[j]]) continue;
            ma[arr[j]] = 1 ;
            answer++;
        }
    cout << answer;
}

 

[배울 점]

- int는 4바이트, long은 32비트 시스템에서 4바이트 64비트 시스템에서 8바이트, long long은 8바이트

- 위에서 1 << 19로 쓰면 안됨. 1은 int형이기 때문에 16비트가 최대이므로 1LL을 사용해야함.