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

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

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

1898

527

405

28.867%

문제

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번째 줄까지 각 줄에 명령이 주어진다. 

출력

은하수를 건널 수 있는 기차의 수를 출력하시오.

#include <iostream>
#include <vector>
#include <set>
#include<algorithm>
#include <memory.h>
using namespace std;
 

int n,m;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    vector<int> v(n+1,0);
    while(m--){
        int num, idx, seat;
        cin >> num;
        switch (num) {
            case 1:
                cin >> idx >> seat;
                v[idx] |= (1<<(seat-1));
                break;
            case 2:
                cin >> idx >> seat;
                v[idx] &= ~(1 << (seat - 1));
                break;
            case 3:
                cin >> idx;
                v[idx] = v[idx] << 1 ;
                v[idx] &= ((1 << 20) - 1);
                break;
            default:
                cin >> idx;
                v[idx] = v[idx] >> 1;
                break;
        }
    }
    set<int> s;
    for(int i=1; i<=n; i++){
        s.insert(v[i]);
    }
    cout << s.size();
    return 0;
}

명령을 어떻게 코드로 구현하느냐가 핵심인 문제였다.
일단 아무도 타지 않은 기차를 0이 20개인 비트라고 생각하면서 문제를 풀이해야한다.

스위치문으로 분기를 만들어주고 입력한 명령에따라서 코드가 실행될 수 있도록 만들어주었다.

• 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다.
  
  
  v[idx] |= (1<<(seat-1));-> x번째 비트를 1로 바꾸어 주면 되는 명령이다. 좌석이 1번부터 시작하나 비트는 0번부터 시작하기 때문에 seat-1을 1로 바꿔준 후 그 비트를 기존의 비트와 or연산하여 무조건 x번째 비트가 1이 될 수 있도록 한다.
• 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다.
  
  
  v[idx] &= ~(1 << (seat - 1));->x번째 비트를 0으로 바꾸어주면 되는 명령이다. seat-1을 1로 바꾼후 그것을 not처리 하여 x번째만 0, 다른 비트들은 1이 되도록 만들고 기존의 비트들과 and 연산을 해 x번째는 무조건 0이 될 수 있도록 한다.

• 3 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 뒤로간다. k번째 앉은 사람은 k+1번째로 이동하여 앉는다. 만약 20번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
  
  
  v[idx] = v[idx] << 1 ;v[idx] &= ((1 << 20) - 1);->비트들을 모두 왼쪽 시프트처리를 하여 1칸씩 이동시켜준다. 20번째 사람이 왼쪽 시프트를 할 경우 21번째 비트가 발생하기때문에 이를 제거해준다.

• 4 i : i번째 기차에 앉아있는 승객들이 모두 한칸씩 앞으로간다. k번째 앉은 사람은 k-1 번째 자리로 이동하여 앉는다. 만약 1번째 자리에 사람이 앉아있었다면 그 사람은 이 명령 후에 하차한다.
  
  
  v[idx] = v[idx] >> 1;-> 비트들을 모두 오른쪽 시프트 처리를 하여 1칸씩 이동시켜준다.

 

처음 풀어보는 비트마스킹 문제였다. 논리회로나 컴퓨터 구조를 공부할때도 비트연산에 약한 편이었어서 풀기도 전에 겁부터 먹었었는데 의외로 꽤 쉽고? 재밌는 문제였다. 비트마스킹 초보자들이 풀면 좋을것 같은 문제!