백준 15662번 톱니바귀 (2)[골드 5][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 구현 + 시뮬레이션입니다. 말 그대로 문제에서 요구한 내용을 구현을 할 수 있는지 묻는 문제입니다. 톱니바퀴가 여러 개 주어지고 회전 조건이 있습니다. 회전 조건을 잘 해석해서 풀이하신다면 문제없이 풀이할 수 있습니다.

 

2. 문제 풀이

 톱니바퀴는 시계방향 또는 반시계방향으로 회전합니다. 저는 톱니바퀴를 선형으로 관리했는데 양방향 회전에서 시간복잡도가 효율적인 자료구조 덱을 선택했습니다. C++에서 덱은 배열처럼도 사용할 수 있는데요. 덕분에 자료구조를 택하는 데에는 어려움이 없었습니다. 주어지는 톱니바퀴 번호와 회전 방향을 기준으로 오른쪽 톱니와 왼쪽 톱니의 회전 방향을 결정해 준 다음 linear 하게 회전시켜 주는 과정을 k번 반복하시면 됩니다. 12시 방향 데이터는 덱에서 front() 값이므로 모두 더해주시고 출력하시면 쉽게 풀 수 있습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int LEFT = 6;
const int RIGHT = 2;

int n, k;
deque<int> wheel[1005];
int d[1005];

void decide_diretion(int cur, int dir) {
    memset(d, 0, sizeof(d));
    d[cur] = dir;
    for(int i = cur; i < n - 1; i++) {
        if(wheel[i][RIGHT] == wheel[i + 1][LEFT]) {
            break;
        }
        d[i + 1] = d[i] * -1;
    }

    for(int i = cur; i > 0; i--) {
        if(wheel[i][LEFT] == wheel[i - 1][RIGHT]) {
            break;
        }
        d[i - 1] = d[i] * -1; 
    }
}

void rotate(int idx, int dir) {
    decide_diretion(idx, dir);

    for(int i = 0; i < n; i++) {
        if(!d[i]) {
            continue;
        }

        if(d[i] < 0) {
            wheel[i].pb(wheel[i].front());
            wheel[i].pop_front();
        }
        else {
            wheel[i].push_front(wheel[i].back());
            wheel[i].pop_back();
        }
    }
}

int main() {
    fastio(nullptr, false);

    cin >> n;
    for(int i = 0; i < n; i++) {
        string cur;
        cin >> cur;
        for(int j = 0; j < sz(cur); j++) {
            wheel[i].pb(cur[j] - '0');
        }
    }
    
    cin >> k;
    while(k--) {
        int idx, dir;
        cin >> idx >> dir;
        rotate(idx - 1, dir);
    }

    int ans{};
    for(int i = 0; i < n; i++) {
        ans += wheel[i].front();
    }

    cout << ans;
}

 

4. 제출결과