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

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터

www.acmicpc.net

 

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 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의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #define LEFT_T 6 // 왼쪽 톱니바퀴 index
  6. #define RIGHT_T 2 // 오른쪽 톱니바퀴 index
  7. using namespace std;
  8. int k;
  9. vector< vector<int> >t(4);
  10.  
  11. void left(vector<int>& v){
  12. rotate(v.begin(), v.begin()+1, v.end());
  13. }
  14.  
  15. void right(vector<int>& v){
  16. rotate(v.rbegin(), v.rbegin()+1, v.rend());
  17. }
  18.  
  19. void rotate(vector<int>& v, int t_dir){
  20. if(t_dir == 1) right(v);
  21. else left(v);
  22. }
  23.  
  24. void propagate(int prev_idx, int t_dir, int prop_dir){
  25. // prev_idx : 회전을 전파한 톱니바퀴
  26. // t_dir : 이전 톱니바퀴가 회전한 방향
  27. // prop_dir : propagation의 방향
  28.  
  29. int cur_t = prev_idx + prop_dir;
  30. if(cur_t < 0 || cur_t > 3) return;
  31.  
  32. int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  33. int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
  34.  
  35. if(prop_dir == -1){ //left propagation
  36. if(cur_tr != prev_tl){
  37. propagate(cur_t, -t_dir, prop_dir);
  38. } else return;
  39. } else {
  40. if(prev_tr != cur_tl){ // right propagation
  41. propagate(cur_t, -t_dir, prop_dir);
  42. } else return;
  43. }
  44. rotate(t[cur_t], -t_dir);
  45. }
  46.  
  47. int main(){
  48. for(int i=0;i<4;i++){
  49. for(int j=0; j<8; j++){
  50. int m;
  51. scanf("%1d", &m);
  52. t[i].push_back(m);
  53. }
  54. }
  55. scanf("%d", &k);
  56. for(int i=0; i<k; i++){
  57. int cur_t, rot;
  58. scanf("%d%d", &cur_t, &rot);
  59. cur_t -= 1;
  60.  
  61. // 왼쪽 전파
  62. propagate(cur_t, rot, -1);
  63. // 오픈쪽 전파
  64. propagate(cur_t, rot, 1);
  65.  
  66. // 현재 톱니바퀴 회전
  67. rotate(t[cur_t], rot);
  68. }
  69.  
  70. int ans = 0;
  71. for(int i=0;i<4;i++){
  72. ans += t[i][0] << i;
  73. }
  74. printf("%d\n",ans);
  75. return 0;
  76. }
  77.  

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

+ Recent posts