백준 14891번 톱니바퀴 (C++)

문제 링크 : www.acmicpc.net/problem/14891

14891번: 톱니바퀴

푸는 방법은 여러가지가 있겠지만, 나는 톱니바퀴의 모든 값들을 회전시키는것이 아닌 정답에 영향을 주는 3가지 위치를 회전 시키는 방법을 선택했다.

 

 

 

위 사진의 맨 위(정답위치)는 첫 번째 자리(=1), 오른쪽은 두 번째 자리 (=3), 왼쪽은 세 번째 자리(=7)로 칭했다.

 

문제 풀이는 다음과 같다.

1. 톱니바퀴의 값을 입력 받는다. 이때 주어지는 값은 숫자가 아닌 문자형이므로, 편의상 문자형을 숫자형으로 변환하여 값을 저장한다.

    for(int i=1; i<=4; i++){
        for(int j=1; j<=8; j++){
            cin >> c;
            arr[i][j] = c-'0';
        }
    }

2. 모든 톱니바퀴의 중요한 자리 3개의 값을 저장한다. 고정적으로 위 사진속의 첫 번째 자리는 1, 두 번째 자리는 3, 세 번째 자리는 7로 저장한다.

    for(int i=1; i<=4; i++){
        idx[i][0] = 1;
        idx[i][1] = 3; 
        idx[i][2] = 7;
    }

3. 회전할 톱니바퀴와 회전 방향을 저장하기 위한 pair타입 벡터를 생성한다.

모든 값을 저장 한 뒤, call by reference로 벡터를 인자로 넘긴다.

    vector<pair<int,int>> v(r);
    for(int i=0; i<r; i++){
        cin >> a >> b;
        v[i] = {a,b};
    }
    for(int i=0; i<r; i++)go(v,i);

4. 아래 함수는 call by reference로 벡터를 인자로 넘긴 함수이다.

void go(vector<pair<int,int>> &v, int n){
    int pos = v[n].first, dir = v[n].second;
    m[pos] = dir;
    ...

톱니바퀴의 움직임을 저장할 m배열에 최초로 움직이는 톱니바퀴의 위치와 방향을 먼저 저장해준다.

 

5. 아래 코드는 최초로 회전하는 톱니바퀴를 기준으로 왼쪽으로 회전여부를 결정하는 for문이다.

    for(int i=pos-1; i>0; i--){
        if(m[i+1]==0) continue;
        if(arr[i+1][idx[i+1][2]]!=arr[i][idx[i][1]]){
            if(abs(pos-i)%2==1){ 
                if(dir==1) m[i] = -1;
                else m[i] = 1;
            }
            else m[i] = dir;
        }
        else m[i] = 0;
    }

맨 첫 번째 문장이 중요한데, 만약 이전 톱니바퀴가 움직이지 않을 경우, 현재 톱니바퀴또한 움직일 수 없으므로 continue를 진행해준다.

이전 톱니바퀴의 두 번째 자리와 현재 톱니바퀴의 세 번째 자리의 값이 다를 경우, 회전을 진행해준다.

반대로 값이 같을 경우 회전을 진행하지 않고 회전값은 0으로 저장해준다.

 

회전을 할 경우 이전 톱니바퀴와 값을 비교해도 상관없지만, 나는 최초로 회전을 하는 톱니바퀴와 비교를 진행했다.

최초로 회전을 하는 톱니바퀴로부터 홀수번째 위치에 존재하면, 최초로 움직이는 톱니바퀴와는 반대로 움직인다.

반대로 짝수 번째 위치에 존재할 경우, 최초로 움직이는 톱니바퀴와 같은 방향으로 움직인다.

 

6. 아래 코드는 최초로 회전하는 톱니바퀴를 기준으로 오른쪽으로 회전여부를 결정하는 for문이다.

    for(int j=pos+1; j<=4; j++){
        if(m[j-1]==0) continue;
        if(arr[j-1][idx[j-1][1]]!=arr[j][idx[j][2]]){
            if(abs(j-pos)%2==1){
                if(dir==1) m[j] = -1;
                else m[j] = 1;
            }
            else m[j] = dir;
        }
        else m[j] = 0;
    }

핵심 해설은 5번과 동일하다. 다만 오른쪽으로 비교를 진행하므로, 이전 톱니바퀴의 첫 번째 자리와 현재 톱니바퀴의 세 번째 자리의 값을 비교해주면 된다.

 

7. 저장했던 회전값들을 기반으로 톱니바퀴의 핵심자리들을 회전시켜준다.

    for(int i=1; i<=4; i++) if(m[i]!=0) go2(i,m[i]);
    
    ...
    
    void go2(int x, int y){
    if(y==1) y=-1;
    else y = 1;
    for(int i=0; i<3; i++){
        idx[x][i] += y;
        if(idx[x][i]<1) idx[x][i] = 8;
        else if(idx[x][i]>8) idx[x][i] = 1;
    }
}

이때 중요한 점이, 시계 방향이라고 회전이 +1이 되는게 아니라, 오히려 반대로 -1이 된다.

예를들어 시계방향으로 회전이 될 경우, 2번째에 있던 값이 3번째로. 3번째에 있던값이 4번째로 가게 된다. 때문에 3번째 자리에 있는 값은 2번째 자리의 값이 차지하게 되므로, 역으로 -1을 해주어야 핵심 위치들을 회전시킨 결과가 나온다.

 

8. 회전을 시켰으면 회전 배열은 다시 0으로 초기화해준다.

for(int i=1; i<=4; i++) m[i] = 0;

 

9. 모든 계산을 끝내고 배열의 첫 번째 자리에 위치한 값들을 기준으로 점수를 합산한다.

    int score = 1;
    for(int i=1; i<=4; i++){
        if(arr[i][idx[i][0]]==1) ans+=score;
        score*=2;
    }
    cout << ans << "\n";

#include <iostream>
#include <vector>
using namespace std;

int arr[5][9], idx[5][3], m[5] = {0,0,0,0,0}, r, a, b, ans = 0;
char c;

void go2(int x, int y){
    if(y==1) y=-1;
    else y = 1;
    for(int i=0; i<3; i++){
        idx[x][i] += y;
        if(idx[x][i]<1) idx[x][i] = 8;
        else if(idx[x][i]>8) idx[x][i] = 1;
    }
}

void go(vector<pair<int,int>> &v, int n){
    int pos = v[n].first, dir = v[n].second;
    m[pos] = dir;
    for(int i=pos-1; i>0; i--){
        if(m[i+1]==0) continue;
        if(arr[i+1][idx[i+1][2]]!=arr[i][idx[i][1]]){
            if(abs(pos-i)%2==1){ 
                if(dir==1) m[i] = -1;
                else m[i] = 1;
            }
            else m[i] = dir;
        }
        else m[i] = 0;
    }
    for(int j=pos+1; j<=4; j++){
        if(m[j-1]==0) continue;
        if(arr[j-1][idx[j-1][1]]!=arr[j][idx[j][2]]){
            if(abs(j-pos)%2==1){
                if(dir==1) m[j] = -1;
                else m[j] = 1;
            }
            else m[j] = dir;
        }
        else m[j] = 0;
    }
    for(int i=1; i<=4; i++) if(m[i]!=0) go2(i,m[i]);
    for(int i=1; i<=4; i++) m[i] = 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i=1; i<=4; i++){
        for(int j=1; j<=8; j++){
            cin >> c;
            arr[i][j] = c-'0';
        }
    }
    for(int i=1; i<=4; i++){
        idx[i][0] = 1;
        idx[i][1] = 3; 
        idx[i][2] = 7;
    }
    cin >> r;
    vector<pair<int,int>> v(r);
    for(int i=0; i<r; i++){
        cin >> a >> b;
        v[i] = {a,b};
    }
    for(int i=0; i<r; i++)go(v,i);
    int score = 1;
    for(int i=1; i<=4; i++){
        if(arr[i][idx[i][0]]==1) ans+=score;
        score*=2;
    }
    cout << ans << "\n";
    return 0;
}