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

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

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

<풀이>

사용한 알고리즘 : 비트마스킹

 

풀이 전략 : 기본값을 2^20으로 두고 비트마스크를 통해 승객을 태우거나 하차시킨다.                 default=Math.pow(2,20)

 

최초 기차의 상태는 00000 00000 00000 00000 이다.

여기서 비트 마스킹에 사용할 값인 default를 1 00000 00000 00000 00000 로 두고

아래 명령에 따라 변화하는 기차 상태값을 살펴보자.

 

1) 1 i x : i번째 기차 x번째 좌석에 시민을 태운다. 타있던 상태면 현상태 유지

                (i번째 기차 좌석 상태 정수) = default>>x | (i번째 기차 좌석 상태 정수)

         ex1 ) 1 1 5

             train[1] = (00001 00000 00000 00000) | (00000 00000 00000 00000)

                               = 00001 00000 00000 00000

         ex2 ) 1 1 8

             train[1] = (00000 00100 00000 00000) | (00001 00000 00000 00000)

                               = 00001 00100 00000 00000

 

2) 2 i x : i번째 기차 x번째 좌석에 앉아있는 시민을 하차시킨다. 없던 상태면 현상태 유지

                (i번째 기차 좌석 상태 정수) = ~(default>>x) & (i번째 기차 좌석 상태 정수)

         ex ) 2 1 5

             train[1] = ~(00001 00000 00000 00000) | (00001 00100 00000 00000)

                               = (11110 11111 11111 11111) | (00001 00100 00000 00000)

                               = 00000 00100 00000 00000

 

3) 3 i : i번째 기차 승객을 모두 한 칸씩 뒤로 이동시킨다. 20번째 승객은 하차

        ex ) 3 1

             train[1] = 00000 00100 00000 00000 >> 1

                          = 00000 00010 00000 00000

 

4) 4 i : i번째 기차 승객 모두 한 칸씩 앞으로 이동시킨다. 1번째 승객은 하차

        ex ) 4 1

             train[1] = 00000 00010 00000 00000 << 1

                          = 00000 00100 00000 00000

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int train[] = new int[N+1];
		Set<Integer> set = new HashSet<Integer>();
		int defaultNum=(int)Math.pow(2, 20);
		for(int i=0;i<M;++i) {
			st = new StringTokenizer(br.readLine());
			int cmdNum = Integer.parseInt(st.nextToken());
			int trainNum = Integer.parseInt(st.nextToken());
		
			if(cmdNum==1) {
				int position = Integer.parseInt(st.nextToken());
				train[trainNum]=(defaultNum>>position)|train[trainNum];
			}
			else if(cmdNum==2) {
				int position = Integer.parseInt(st.nextToken());
				train[trainNum]=(~(defaultNum>>position))&train[trainNum];
			}
			else if(cmdNum==3) {
				train[trainNum]=train[trainNum]>>1;
			}
			else if(cmdNum==4) {
				train[trainNum]=(int) ((train[trainNum]<<1)%defaultNum);
			}
		}
		for(int i=1;i<N+1;++i) {
			set.add(train[i]);
		}
		System.out.println(set.size());
	}
}