BOJ 14891 톱니바퀴

0. 문제 개요

톱니바퀴가 나열되어 있고 각 톱니에 극이 달려 있다.(n극, s극)

극에 따라 톱니가 돌아갈 때 같이 돌 수도, 돌지 않을 수도 있다.

 

1. 문제 해결 아이디어

(1) 자료구조 : 톱니정보를 담고 그것을 이동(shift)시켜야 한다. -> bitset

(2) 톱니를 회전시킬 때는 rotate shift를 이용하자.

 

당연히 c++에 rotate shift를 구현한 stl이 있을 줄 알았는데 없었다..

그래서 구글링을 해보니 다음과 같이 rotate shift를 구현할 수 있었다.

 

x << 움직이고 싶은 정도  |  x>> (비트 수 - 움직이고 싶은 정도)

 

예를 들어 8bit 짜리 bitset x 을 오른쪽으로 두 칸 이동시키고 싶다면,

x >> 2 | x << (8-2)

 

간단하게 원리를 살펴보면, x를 알기 쉽게 abcdefgh 라고 가정하자.

이 때 우리가 얻고 싶은 결과는 ghabcdef 이다.

(1) x >> 2 의 결과    

00abcdef        //먼저 이동하고 싶은 만큼 옮긴다.

 

(2) x << (8-2) 의 결과

gh000000      //(1)에서 shift로 0으로 바뀐 bit들을 보정해준다.

 

(3) (1)과 (2)의 결과를 or 연산한 결과 (x >>2 | x<< 6)

ghabcdef

 

 

2. 코드

#include <iostream>
#include <bitset>
#include <string>
using namespace std;
bitset<8> a[4];
int n;
void rot(int i, int opt) {        
    if (opt == -1) {                                    //반시계 방향
        a[i] = (a[i] << 1) | (a[i] >> 7);
    }
    else                                                //시계 방향
        a[i] = (a[i] >> 1) | (a[i] << 7);
}
 
void solve(int i, int opt) {
    
    switch (i)
    {
    case 0:
        if (a[i][5] + a[i+1][1] == 1) {                    //0,1
            if (a[i + 1][5] + a[i + 2][1] == 1) {        //1,2
 
                if (a[i + 2][5] + a[i + 3][1] == 1)     //2,3
                    rot(3, -1* opt);
                
                rot(2,  opt);
            }
            rot(1, -1* opt);
        }
        rot(0, opt);
        break;
            
    case 1:
        if (a[i - 1][5] + a[i][1] == 1) {                //0,1
            rot(0, -1*opt);
        }
 
        if (a[i][5] + a[i + 1][1] == 1) {                //1,2
            if (a[i + 1][5] + a[i + 2][1] == 1)         //2,3
                rot(3,  opt);
            rot(2, -1* opt);
        }
        rot(1, opt);
        break;
            
    case 2:
        if (a[i][5] + a[i+1][1] == 1) {                    //2,3
            rot(3, -1*opt);
        }
        if (a[i-1][5] + a[i][1] == 1) {                    //1,2
            if (a[i-2][5] + a[i-1][1] == 1)             //0,1
                rot(0, opt);
            rot(1, -1* opt);
        }
        rot(2, opt);
        break;
            
    case 3:
        if (a[i-1][5] + a[i][1] == 1) {                    //2,3
            if (a[i - 2][5] + a[i - 1][1] == 1) {        //1,2
                if (a[i - 3][5] + a[i - 2][1] == 1)      //0,1
                    rot(0, -1*opt);
                rot(1, opt);
            }
            rot(2, -1* opt);
        }
        rot(3, opt);
        break;
            
    default:
        break;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //freopen("input.txt", "r", stdin);
    
    string str;
    
    for (int i = 0;i < 4;i++) {
        cin >> str;
        a[i] = bitset<8>(str);
        
    }
    
    cin >> n;
    int i, opt;
    while (n--) {
        cin >> i >> opt;
        solve(i-1, opt);
    }
    
    cout << a[0][7] + a[1][7] * 2 + a[2][7] * 4 + a[3][7] * 8;
    
    return 0;
}

 

3. 나오며...

- bitset 은 배열 순서가 일반적인 배열과 반대이다. [7][6][5][4][3][2][1][0]

- 문자열을 이용해 bitset을 초기화할 수 있다.

- 톱니바퀴의 개수가 4개로 한정되어 톱니바퀴가 돌 수 있는 모든 경우를 고려해주었는데,

  이를 더 간단하게 구현할 순 없을까? 규칙이 없을까?