백준 14891번 - 톱니바퀴

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

처음에 너무 복잡하게 생각했었는데 사실 엄청 간단하게 해결할 수 있었다.

 

문제가 다행히도 매번 톱니바퀴가 회전할 때마다 상태가 변화한 것을 체크해야 하는 것이 아니고 처음 상태에서 회전할 건지 안 할 건지만 판단해주면 되는 문제였다.

 

아마 이 문제에서의 핵심은 X번 톱니바퀴를 회전시켰을 때 양 옆의 톱니바퀴가 회전할지 안 할지 구하고, 또 양 옆의 톱니바퀴가 회전할지 안 할지 구해야 하는 부분이 가장 구현하기 까다로웠을 것이다.

 

나는 left와 right란 변수를 두어 범위 안에만 존재한다면 계속 반복할 수 있게 만들었다.

(이게 말로 설명하기 그렇고 아래 코드를 보면 이해하기 쉬움)

 

다행히도? 톱니바퀴가 4개였기 때문에 시간복잡도는 매우 넉넉했다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
typedef pair<bool, int> pbi;
 
deque<char>dq[4];
pbi turn[4];
 
void init() {
    for (int i = 0; i < 4; i++) {
        turn[i] = pbi(false, 0);
    }
}
 
int main() {
    int n, k, num, dis;
    string str;
    for (int i = 0; i < 4; i++) {
        cin >> str;
        for (int j = 0; j < str.size(); j++) {
            char temp = str[j] == '0' ? 'N' : 'S';  // N극과 S극 저장
            dq[i].push_back(temp);
        }
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> num >> dis;
        init();
        turn[num - 1] = pbi(true, dis);
        int left = num - 1, right = num - 1;
        int t = 3;
        while (t--) { // 3번만 돌려도 됨. 어차피 모든 경우는 3번 안에서 판별
            left -= 1; right += 1;
            if (0 <= left && left < 3) { // 범위 안에 있다면
                // 해당 톱니바퀴가 오른쪽 톱니바퀴에 영향을 받음
                // 즉 오른쪽 톱니바퀴와 맞닿은 부분을 확인해야 함(서로 상극인지, 이전 톱니바퀴가 회전을 했는지)
                if (dq[left][2] != dq[left + 1][6] && turn[left + 1].first == true) turn[left] = pbi(true, turn[left + 1].second * (-1));
            }
            if (1 <= right && right <= 3) { // 왼쪽과 같이 
                if (dq[right][6] != dq[right - 1][2] && turn[right - 1].first == true) turn[right] = pbi(true, turn[right - 1].second * (-1));
            }
        }
        for (int j = 0; j < 4; j++) {
            if (turn[j].first == true) {
                if (turn[j].second == 1) { // 시계방향 회전
                    dq[j].push_front(dq[j].back());
                    dq[j].pop_back();
                }
                else { // 반시계방향 회전
                    dq[j].push_back(dq[j].front());
                    dq[j].pop_front();
                }
            }
        }
    }
    int ans = 0, mul = 1;
    for (int i = 0; i < 4; i++) {
        if (dq[i][0] == 'S') ans += mul;
        mul *= 2;
    }
    cout << ans << "\n";
}

뭔가 구현 문제는 설명하기가 귀찮다..

 

어쨌든 나쁘지 않은 퀄리티의 문제였다!