[C++] 백준 14891번: 톱니바퀴

🔗 문제

14891번: 톱니바퀴

14891번: 톱니바퀴

 

🖍 풀이

 

더 효율적인 방법이 있나 검색해봤는데 나처럼 푼 사람은 없는 것같아 뿌듯.. (하지만 있을 수도.. )

최대한 배열 복사하기가 싫어서 꼭지점 인덱스를 기준으로 풀었지만, 회전하고 나서 배열 변경해도 시간초과가 나지 않는다. 

deque를 이용해서 풀어도 시간초과는 나지 않는다.

 

1. n번 톱니바퀴를 d방향으로 회전 시킨다.
   1. n번 톱니바퀴를 기준으로 왼쪽은 [n][6] 과 [n-1][2]의 값을 비교한다.
   2. n번 톱니바퀴를 기준으로 오른쪽은 [n][2]와 [n+1][6]의 값을 비교한다.
   3. 각각 왼쪽, 오른쪽의 조건이 맞으면 방향따라 연쇄적으로 조건을 적용시킨다.
2. 회전이 끝나면 톱니바퀴 값은 갱신해준다.

 

톱니바퀴의 회전 방향에 따라 인접 톱니바퀴의 극이 있는 방향이 다르기 때문에 따로 함수를 만들어 주었다.

void rotation(int num, int dir)
{
    rotationRight(num, dir);
    rotationLeft(num, dir);
    pos[num] = (pos[num] + dir*-1 + 8) % 8;
}

 

왼쪽방향은 [n][6] 과 [n-1][2]의 값을 비교해야 한다.

 

pos[num]이 num번 톱니바퀴의 맨 위 꼭지점 인덱스를 저장해주었다.

 

원형큐처럼 size + pos[num] + 이동하려는 칸) % size 로 꼭지점을 기준으로 오른쪽, 왼쪽의 인덱스를 알 수 있다.

1. 조건이 맞으면 연쇄적으로 그 방향 진행
2. 진행이 끝난 후 꼭지점 갱신

void rotationLeft(int num, int dir)
{
    if(num-1 == -1) return;
    
    int now = (pos[num]+6) % 8; // 현재 톱니바퀴의 왼쪽 극성
    int next = (pos[num-1]+2) % 8; // 현재 톱니바퀴 왼쪽에 있는 맞물리는 극성

    if(gears[num][now] != gears[num-1][next]) // 회전하자.
    {
        rotationLeft(num-1, (dir*-1)); // 반대 방향으로 회전한다. 

        // 반대로 회전하기 떄문에 꼭지점 인덱스가 dir만큼 이동
        pos[num-1] = (pos[num-1] + dir + 8) % 8; 
    }
}

 

주의사항

-1 (반시계방향)으로 회전하면 배열 인덱스의 꼭지점이 ‘증가’하기 때문에 d*-1 해준다.

반 시계방향 회전 전: 10111111 // 0의 인덱스 1
반 시계방향 회전 후: 01111111 // 0의 인덱스 2

// -1 방향으로 이동했을 때 배열 인덱스상으로는 -1*-1 = 1 이동했다.

 

while(K--)
{
    std::cin >> num >> d;
    rotation(num, d);
}

... 

void rotation(int num, int dir)
{
    rotationRight(num, dir);
    rotationLeft(num, dir);
    pos[num] = (pos[num] + dir*-1 + 8) % 8;
}

 

💾  소스

#include <iostream>

char gears[5][8];
int pos[5] = {0, };

void rotationRight(int num, int dir)
{
    if(num+1 == 5) return;
        
    int now = (pos[num]+2)%8;
    int next = (pos[num+1]+6)%8;
    
    if(gears[num][now] != gears[num+1][next])
    {
        rotationRight(num+1, (dir*-1));
        pos[num+1] = (pos[num+1] + dir + 8) % 8;
    }
}

void rotationLeft(int num, int dir)
{
    if(num-1 == -1) return;
    
    int now = (pos[num]+6) % 8;
    int next = (pos[num-1]+2) % 8;

    if(gears[num][now] != gears[num-1][next])
    {
        rotationLeft(num-1, (dir*-1));
        pos[num-1] = (pos[num-1] + dir + 8) % 8;
    }
}

void rotation(int num, int dir)
{
    rotationRight(num, dir);
    rotationLeft(num, dir);
    pos[num] = (pos[num] + dir*-1 + 8) % 8;
}

int main()
{
    int K, N, D;
    for(int i=1; i<5; ++i)
    {
        for(int j=0; j<8; ++j)
        {
            std::cin >> gears[i][j];
        }
    }
    
    std::cin >> K;

    while(K--)
    {
        std::cin >> N >> D;
        rotation(N, D);
    }
    
    int answer = 0;
    for(int i=1; i<5; ++i)
    {
        if(gears[i][pos[i]]=='1')
            answer += (1 << (i-1));
    }
    
    std::cout << answer;
    
    return 0;
}