[백준][파이썬] 15787번

 

꼭 이진수끼리의 비트 연산을 하겠다고 하다가.. 멍고생했다

 

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

문제

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

출력

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

링크

15787번: 기차가 어둠을 헤치고 은하수를 (acmicpc.net)

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

 

 접근 방법

1. 기차의 수만큼 리스트에 원소를 추가하여 인덱스로 접근할 수 있도록 한다.
2. 명령에 맞게 if문을 작성한다.
   1. 승차일 때는 OR 연산
   2. 하차일 때는 AND 연산
   3. 자리 이동일 때는 SHIFT 연산
3. 기차 리스트 내에서 중복인 원소를 제거한다. 

완전 탐색 참고 자료 : [알고리즘][파이썬] Exhaustive Search / 완전 탐색 — y-seo의 딩코 기록들 (tistory.com)

[알고리즘][파이썬] Exhaustive Search / 완전 탐색

 

 풀이

1. 2진수 ↔ 10진수

2진수끼리의 비트 연산을 위해 2진수와 10진수 간의 변환이 잦았다. 내가 사용한 함수들을 정리해보고자 한다.

우선 10진수 → 2진수의 변환은 bin 함수를 통해 가능하다. '0b'는 2진수임을 나타내는 접두어이고 이 함수의 결과값은 문자열 타입을 가진다.

>>> bin(0)
'0b0'
>>> bin(2)
'0b10'

2진수 → 10진수의 변환은 int 함수를 통해 가능하다. 이때는 문자열을 정수 타입으로 변환해준다. 따라서 위의 bin 함수와 함께 사용하기 좋다.

>>> int('0b111100', 2)
60

 

 전체코드

n, m = map(int,input().split( ))
train = [0] * n

for j in range(m): #명령 받기
    menu = list(map(int,input().split()))
    i = menu[1] - 1

    if menu[0] == 1: #승차
        x = menu[2] - 1
        cnt = int(bin(2**x), 2 )
        train[i] = int(bin(train[i] | cnt), 2)
    elif menu[0] == 2: #하차
        x = menu[2] - 1
        cnt = int(bin(2**20-1-2**x), 2 )
        train[i] = int(bin(train[i] & cnt), 2)
    elif menu[0] == 3: #한 칸씩 뒤로
        train[i] = int(bin(train[i]),2) << 1
        if train[i] > 2**19:
            train[i] = int(bin(train[i] & 0b011111111111111111111), 2)
    elif menu[0] == 4: #한 칸씩 앞으로
        train[i] = int(bin(train[i]),2) >> 1

train = set(train) #중복 제거
print(len(train))