BOJ 14891 톱니바퀴

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 k번 회전 시켰을 때,

톱니바퀴의 변화를 잘 구현해야하는 문제이다.

 

톱니바퀴는 다음과 같이 반시계방향 / 시계방향으로 회전할 수 있다.

 

톱니바퀴의 수는 다음과 같이 4개로 고정돼 있다. 그리고 맞닿아 있는 극이 다를 경우 회전이 영향받는다. 즉, 만약 1 번 톱니바퀴가 반시계방향으로 회전하는 경우 2번째 톱니바퀴의 맞닿아 있는 극이 서로 다르므로, 2번 째 톱니바퀴는 반대방향인 시계방향으로 회전한다. 그리고 2번 톱니바퀴와 3번 톱니바퀴의 맞닿아 있는 극은 같기 때문에 2번이 회전할 때 3번 톱니바퀴는 회전하지 않는다.

 

 

 

그럼 문제는 이해했고, 회전을 어떻게 구현할까.

CPP 에는 rotate 라는 함수를 지원한다. 입력에서 8개의 정수로 N,S 극을 표현하기 때문에, 회전 시 rotate함수로 배열을 적절히 회전시킬 수 있다. 만약 rotate를 사용하지 않는다면, 각 톱니바퀴의 현재 left / right 의 극 index를 저장하는 방법이 있겠다. 

 

개인적으로 시뮬레이션 문제를 풀 때는 직관적인 것이 풀기 편해 rotate를 사용했다.

 

# rotate 사용법

#include <vector>
#include <iostream>
#include <algorithm>
 
auto print = [](auto const& remark, auto const& v) {
    std::cout << remark;
    for (int n: v)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
 
    print("before sort:\t\t", v);
 
    // insertion sort
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }
 
    print("after sort:\t\t", v);
 
    // simple rotation to the left
    std::rotate(v.begin(), v.begin() + 1, v.end());
 
    print("simple rotate left:\t", v);
 
    // simple rotation to the right
    std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
 
    print("simple rotate right:\t", v);
}

Output :

before sort:            2 4 2 0 5 10 7 3 7 1 
after sort:             0 1 2 2 3 4 5 7 7 10 
simple rotate left:     1 2 2 3 4 5 7 7 10 0 
simple rotate right:    0 1 2 2 3 4 5 7 7 10

 

 

k 번 톱니바퀴를 회전 시키는데, 각 회전마다 왼쪽 / 오른쪽 회전이 전파돼야 한다. 

전파를 위해 propagate 함수를 정의 했다. propagate의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

 

 

소스코드

 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define LEFT_T 6 // 왼쪽 톱니바퀴 index
#define RIGHT_T 2 // 오른쪽 톱니바퀴 index
using namespace std;
int k;
vector< vector<int> >t(4);
 
void left(vector<int>& v){
  rotate(v.begin(), v.begin()+1, v.end());
}
 
void right(vector<int>& v){
  rotate(v.rbegin(), v.rbegin()+1, v.rend());
}
 
void rotate(vector<int>& v, int t_dir){
  if(t_dir == 1) right(v);
  else left(v);
}
 
void propagate(int prev_idx, int t_dir, int prop_dir){
  // prev_idx : 회전을 전파한 톱니바퀴
  // t_dir : 이전 톱니바퀴가 회전한 방향
  // prop_dir : propagation의 방향
 
  int cur_t = prev_idx + prop_dir;
  if(cur_t < 0 || cur_t > 3) return;
 
  int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
 
  if(prop_dir == -1){ //left propagation
    if(cur_tr != prev_tl){
      propagate(cur_t, -t_dir, prop_dir);
    } else return;
  } else {
    if(prev_tr != cur_tl){ // right propagation
      propagate(cur_t, -t_dir, prop_dir);
    } else return;
  }
  rotate(t[cur_t], -t_dir);
}
 
int main(){
  for(int i=0;i<4;i++){
    for(int j=0; j<8; j++){
      int m;
      scanf("%1d", &m);
      t[i].push_back(m);
    }
  }
  scanf("%d", &k);
  for(int i=0; i<k; i++){
    int cur_t, rot;
    scanf("%d%d", &cur_t, &rot);
    cur_t -= 1;
 
    // 왼쪽 전파
    propagate(cur_t, rot, -1);
    // 오픈쪽 전파
    propagate(cur_t, rot, 1);
 
    // 현재 톱니바퀴 회전
    rotate(t[cur_t], rot);
  }
 
  int ans = 0;
  for(int i=0;i<4;i++){
    ans += t[i][0] << i;
  }
  printf("%d\n",ans);
  return 0;
}