[삼성 기출 문제] 백준 14891 톱니바퀴

문제 링크

어떻게 풀까?

전형적인 시뮬레이션 문제입니다. 문제의 내용을 그대로 구현해야합니다!

먼저 생각해보아야 할 것은 톱니바퀴의 극을 어떻게 설정할 것인가? 입니다.

톱니바퀴는 N극과 S극의 2 가지 상태로 나타낼 수 있습니다.

그리고 톱니가 8개이기 때문에, 비트로 나타내면 편하게 관리할 수 있을 것 같습니다!

시계 방향과 반시계 방향도 비트 연산자 하나만으로 해결 될 수 있죠!

struct TOP {
    int topni;
    bool getUP() {
        return topni & 1;
    }
    bool getRIGHT() {
        return topni & (1 << 2);
    }
    bool getLEFT() {
        return topni & (1 << 6);
    }
 
    void rotate(int dir) {
        if (dir == 1) {
            bool temp = topni & 0b10000000;
            topni <<= 1;
            topni |= temp;
            topni &= 0xff;
        }
        else if(dir == -1){
            bool temp = topni & 1;
            topni >>= 1;
            topni |= (temp << 7);
        }
    }
    void set(int v) {
        for (int i = 0; i < 8; i++) {
            topni <<= 1;
            topni += v % 10;
            v /= 10;
        }
    }
}tops[5];

제가 만든 톱니바퀴 구조체 입니다.

톱니바퀴는 머리부분을 0번째 비트로 해서 시계방향으로 정보를 저장합니다.

문제에서 처럼 N극은 0, S극은 1 입니다.

함수를 살펴봅시다.

set을 통해 int로 받은 톱니바퀴를 비트로 변환합니다.

위와 같은 톱니바퀴는 비트로 나타내면 11110101 이 되겠죠!

이번에는 rotate를 봅시다.

1. 8번째 톱니는 1번째 톱니로 와야하므로 7번 비트를 우선 저장합니다.

2.시계 방향으로 돌리면 0번 비트가 1번 비트로 가야하기 때문에 왼쪽으로 1칸 쉬프트 연산을 해줍니다.

3. 저장했던 7번 비트를 0번 비트로 넣어줍니다.

 왼쪽으로 1번 쉬프팅하면서 7번비트가 8번 비트로 이동했습니다. 8번 비트에 1이 있을 수도 있다는 것이죠!

4. 이 정보를 지워주기 위해 마지막에 0b11111111과 & 연산을 합니다!

위 톱니를 시계방향으로 돌리면

1. 7번 비트 저장 (temp = 0b10000000)

2. 1 11101010 (왼쪽으로 쉬프트)

3. 1 11101011 (7번 비트를 0번 비트로 이동)

4. 0 11101011 (8번 비트제거) 

반시계 방향은 시계 방향과 반대로 하면 됩니다. 시계 방향과 이동하는 것과는 다르게 쓸데없는 정보가 늘어나지 않는다는 것이 다르긴 합니다.

1. 0번 비트 저장

2. 오른쪽으로 1칸 쉬프트

3. 0번 비트를 7번 비트 위치로 이동

이제 톱니에 대한 구조체를 만들었습니다.

다음으로 구현해야할 부분은 톱니바퀴가 연속으로 회전하는 조건입니다.

연속으로 회전할때 가장 중요한 것은 돌아가는 '조건'을 잘 확인하는 것 입니다!

문제를 확인해 봅시다!

문제의 조건을 보면 첫 번째 상태에서 N과 S로 맞물린 톱니바퀴들이 한 바퀴 돌게 됩니다!

즉, 톱니바퀴가 돌면서 극이 다를 때 회전하는 것이 아니라, 회전하기 전에 극이 달랐던 톱니바퀴가 돌아가는 방식인 것 입니다!

따라서 톱니바퀴를 돌리기 전에 미리 돌아야하는 톱니바퀴를 체크 하고, 체크된 톱니바퀴만 돌리는 방식을 써야합니다!

만약, 위의 사진의 경우에서 3번 톱니바퀴를 돌리는 경우엔 어떻게 될까요?

3번 -> 2번 톱니바퀴가 돌지 않기 때문에 1번 톱니바퀴와 2번 톱니바퀴의 극이 서로 다르더라도 1번 톱니바퀴는 회전하지 않습니다.

즉, 아래 그림처럼 톱니바퀴가 회전하는 곳에서 부터 좌, 우로 톱니바퀴를 검사하면서 회전하는지에 대해서 체크를 해야하는 것 입니다.

 

    while (m--) {
        memset(flag, 0, sizeof(flag));
 
        int n, r;
        cin >> n >> r;
        flag[n] = r;
 
        for (int i = n-1; i >= 1; i--) {
            if (tops[i + 1].getLEFT() ^ tops[i].getRIGHT()) { flag[i] = -flag[i + 1]; }
            else break;
        }
 
        for (int i = n + 1; i <= 4; i++) {
            if (tops[i - 1].getRIGHT() ^ tops[i].getLEFT()) flag[i] = -flag[i - 1];
            else break;
        }
        for (int i = 1; i <= 4; i++) {
            tops[i].rotate(flag[i]);
        }
    }

flag배열이 바로 회전에 대한 체크를 해주는 함수입니다.

flag가 1이면 시계 방향 회전, -1이면 반 시계방향 회전입니다. 0일 경우는 회전하지 않습니다.

처음에 flag배열을 체크해줄 때, XOR 연산을 통해서 극이 서로 다른 경우에만 flag배열에 값을 넣습니다. 만약, 서로 같은 극일 경우에는 break를 이용하여 반복문에서 빠져나옵니다.

만약, 극이 서로 같다면 -연산을 통해서 전에 돌았던 방향과 반대 방향으로 flag 배열을 체크해 줄 수 있습니다.

그럼 이제 결과값 출력을 봅시다.

결과값은 톱니들의 머리를 단순히 2 진법으로 나타냈음을 알 수 있습니다.

1번 톱니바퀴는 0번 비트, 2번 톱니바퀴는 1번 비트, 3번 톱니바퀴는 2번 비트, 4번 톱니바퀴는 3번 비트입니다.

톱니바퀴의 머리를 2 진법을 사용해서 나타내서 결과값을 출력합시다!

    int res = 0;
    for (int i = 1; i <= 4; i++) {
        res += (tops[i].getUP() << (i-1));
    }

코드

#pragma once
#include<iostream>
#include<cstring>
 
using namespace std;
 
struct TOP {
    int topni;
    bool getUP() {
        return topni & 1;
    }
    bool getRIGHT() {
        return topni & (1 << 2);
    }
    bool getLEFT() {
        return topni & (1 << 6);
    }
 
    void rotate(int dir) {
        if (dir == 1) {
            bool temp = topni & 0b10000000;
            topni <<= 1;
            topni |= temp;
            topni &= 0xff;
        }
        else if(dir == -1){
            bool temp = topni & 1;
            topni >>= 1;
            topni |= (temp << 7);
        }
    }
    void set(int v) {
        for (int i = 0; i < 8; i++) {
            topni <<= 1;
            topni += v % 10;
            v /= 10;
        }
    }
}tops[5];
 
int flag[5];
 
int main() {
    for (int i = 1; i <= 4; i++) {
        int n;
        cin >> n;
        tops[i].set(n);
    }
 
    int m;
    cin >> m;
    while (m--) {
        memset(flag, 0, sizeof(flag));
 
        int n, r;
        cin >> n >> r;
        flag[n] = r;
 
        for (int i = n-1; i >= 1; i--) {
            if (tops[i + 1].getLEFT() ^ tops[i].getRIGHT()) { flag[i] = -flag[i + 1]; }
            else break;
        }
 
        for (int i = n + 1; i <= 4; i++) {
            if (tops[i - 1].getRIGHT() ^ tops[i].getLEFT()) flag[i] = -flag[i - 1];
            else break;
        }
        for (int i = 1; i <= 4; i++) {
            tops[i].rotate(flag[i]);
        }
    }
 
    int res = 0;
    for (int i = 1; i <= 4; i++) {
        res += (tops[i].getUP() << (i-1));
    }
    cout << res;
 
    return 0;
}
 

시간복잡도

m이 많아질수록 연산이 많아지기 때문에 시간복잡도는 O(m) 입니다.