[백준OJ] 14891번 톱니바퀴

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

---

 

-풀이-

톱니바퀴 배열을 움직인다기 보단, 톱니바퀴 각각의 left,right의 위치를 기억하는 배열을 만들어서 문제를 풀었다. 초기 left=6, right=2로 초기화 시켜준다.

 

먼저 자신을 돌리기 전, 자신의 왼쪽에 있는 바퀴를 재귀함수를 통해 다 돌려주고, 오른쪽에 있는 바퀴를 다 돌려준 뒤, 자신을 돌려주었다. 돌릴때 옆에있는 바퀴가 d방향으로 돈다면, 자신은 -d방향으로 돌아야한다.

왼쪽에 있는 바퀴를 돌릴땐, 자신의 오른쪽 톱니와 이전의 왼쪽 톱니가 다를때, 재귀를 호출하고 돌려주면되고,

오른쪽에 있는 바퀴를 돌릴땐, 자신의 왼쪽 톱니와 이전의 오른쪽 톱니가 다를때, 재귀를 호출하고 돌려주면 된다.

 

재귀함수를 이용하여 톱니바퀴를 k번 돌린 뒤, 전체 톱니바퀴의 12시방향은 (left+2)%8 로 찾으면 된다. 이유는 다음과 같다

 

i번째 톱니(편하게 0부터 1,2,3 으로 정의하자.)의 12시를 확인할 수 있으므로, 4개의 톱니바퀴를 돌며, 12시방향이 S극(1) 이라면, score에 pow(2,i)를 더해주면 된다.

 

-시간복잡도-

오른쪽, 왼쪽 재귀함수 모두 상수시간 안에 가능하므로 O(1), 자신의 방향을 바꾸는 함수 또한 기본 연산이므로 O(1)이 된다. 따라서 총 시간복잡도는 O(K)가 된다.

 

-코드-

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

char arr[4][8];
int lf[4];
int rt[4];
int k;

void mv(int now,int d){
    if(d==1){
        rt[now]=(rt[now]==0?7:rt[now]-1);
        lf[now]=(lf[now]==0?7:lf[now]-1);
    }
    else{
        rt[now]=(rt[now]+1)%8;
        lf[now]=(lf[now]+1)%8;
    }
}

void rolllf(int prev,int now,int d){
    if(now==-1){
        return;
    }
    if(arr[prev][lf[prev]]!=arr[now][rt[now]]){
        rolllf(now,now-1,-d);
        mv(now,d);
    }
    else{
        return;
    }
}
void rollrt(int prev,int now,int d){
    if(now==4){
        return;
    }
    if(arr[prev][rt[prev]]!=arr[now][lf[now]]){
        rollrt(now,now+1,-d);
        mv(now,d);
    }
    else{
        return;
    }
}


int main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    for(int i=0;i<4;i++){
        for(int j=0;j<8;j++){
            cin>>arr[i][j];
        }
        lf[i]=6;
        rt[i]=2;
    }
    cin>>k;
    for(int i=0;i<k;i++){
        int n,d;
        cin>>n>>d;

        n--;
        rolllf(n,n-1,-d);
        rollrt(n,n+1,-d);
        mv(n,d);
        
    }
    int score=0;
    for(int i=0;i<4;i++){
        int ind=(lf[i]+2)%8;
        if(arr[i][ind]=='1'){
            score+=pow(2,i);
        }
    }
    cout<<score<<"\n";
    return 0;
}