백준 14891번 - 톱니바퀴

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

14891번: 톱니바퀴

 

• 문제 해결 방법

나머지 연산을 잘 이용하면 문제를 쉽게 해결할 수 있습니다.

아래의 그림은 톱니바퀴의 시계방향 회전과 그 상태정보를 0~7인덱스로 나타낸 그림입니다.

톱니바퀴의 시계방향 회전

위 그림과 같이 톱니바퀴의 상태정보를 0~7로 인덱싱하고 12시방향의 상태정보 인덱스를 now라고 한다면,비교해야 할 위치는 다음과 같습니다.

 

오른쪽과 맞닿은 톱니바퀴 인덱스 = (now+2)%8

왼쪽과 맞닿은 톱니바퀴 인덱스    = (now+8-2)%8

(왼쪽 인덱스에서 (+8-2)를 해주는 이유는 %연산시 피연산자가 음수일때 기대와는 다른 값이 나올 수 있기 때문)

 

위와 같이 정의했다면 톱니바퀴들의 상태정보를 비교하여 움직여야 할 톱니바퀴가 몇개인지 구할 수 있습니다.

시계방향으로 움직인다면 12시방향 인덱스(now)에 -1을 해주고 반시계방향으로 움직인다면 now에 +1을 해주면 됩니다.

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N,M;
int m[4][8]{};
int now[4]{};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string str;
    for(int i=0; i<4; i++){
        cin>>str;
        for(int j=0; j<8; j++) 
            m[i][j] = str[j]-'0';
    }

    cin>>M;
    int a,b;
    for(int i=0; i<M; i++){
        cin>>a>>b; 
        a--; // 톱니바퀴 인덱스 0부터
        
	// 움직여야할 톱니바퀴 개수 탐색 ( l번~ r번 )
        int l=a, r=a;
        for(int j=a-1; j>=0; j--){
        	// XOR 연산자로 왼쪽, 오른쪽 상태정보를 확인
            if(m[j][(now[j]+2)%8] ^ m[j+1][(now[j+1]+6)%8]) l--;
            else break;
        }
        for(int j=a+1; j<4; j++){
        	// XOR 연산자로 왼쪽, 오른쪽 상태정보를 확인
            if(m[j][(now[j]+6)%8] ^ m[j-1][(now[j-1]+2)%8]) r++;
            else break;
        }
        
        if(!((a-l)%2)) b *= -1;
        for(int k=l; k<=r; k++){
            now[k] = (now[k]+8+b)%8;
            b *= -1;
        }
    }

    int res = 0, power = 1;
    for(int i=0; i<4; i++){
        res += (m[i][now[i]] * power);
        power*=2;
    }
    cout<<res;
}