🥚

Recent Notes

See 20 more →

BOJ - 톱니바퀴(14891)

5 min read

실버1 : 구현 문제이다.

생각

단순 구현 문제이다. 비트마스크 연습을 위해 비트마스크로 풀었다. 해당 과정을 하는 동안에 인접행렬 같은 matrix를 만들어 무언가를 해보려 했지만 좋지 못했다. 구현 문제는 노가다로 적어주는게 정신 건강에 이롭다.

Pseudo-algorithm

  1. 입력을 받는다.
  2. 어떤 톱니바퀴를 돌리는 지 판단한다.
  3. 그 톱니바퀴를 돌렸을 때, 따라서 돌아가는 톱니바퀴의 방향을 정한다.
  4. 그 구한 톱니 바퀴의 방향대로 돌린다.
  5. 마지막에 답을 구한다.

특정 톱니바퀴를 돌렸을 때, 따라서 돌아가는 것의 숫자를 0이면 돌아가지 않는다. 1이면 시계방향, -1이면 반시계방향으로 정하여 구해주었다.

vector<int> getAction(int gear, int dir){
    vector<int> action(5);
    if (gear == 1) {
        action[1] = dir;
        if (isRevolve(1, 2)) action[2] = -action[1];
        if (isRevolve(2, 3)) action[3] = -action[2];
        if (isRevolve(3, 4)) action[4] = -action[3];
    } else if (gear == 2) {
        action[2] = dir;
        if (isRevolve(1, 2)) action[1] = -action[2];
        if (isRevolve(2, 3)) action[3] = -action[2];
        if (isRevolve(3, 4)) action[4] = -action[3];
    } else if (gear == 3) {
        action[3] = dir;
        if (isRevolve(2, 3)) action[2] = -action[3];
        if (isRevolve(3, 4)) action[4] = -action[3];
        if (isRevolve(1, 2)) action[1] = -action[2];
    } else {
        action[4] = dir;
        if (isRevolve(3, 4)) action[3] = -action[4];
        if (isRevolve(2, 3)) action[2] = -action[3];
        if (isRevolve(1, 2)) action[1] = -action[2];
    }
    return action;
}

특정 톱니 바퀴가 돌아갈 때, 이전 상태가 돌아갈 수 있는 상태라면, 인접한 톱니바퀴의 방향은 무조건 반대 방향인 것을 사용했다. 또한 이전 상태의 양극이 반대라 특정 톱니 바퀴가 돌아가게 되면 인접한 톱니바퀴 역시 돌아갈 수 있음에도 불구하고 특정 톱니가 돌아가지 않으면 0을 리턴하므로 인접 톱니도 돌아가지 않는다.

참, 비트가 켜져있는지 아닌지 구분할 때에는 꼭 괄호를 써서 생각하자.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
int state[5];
int N, ans = 0;
 
bool isRevolve(int i, int j){
    if ((state[i] & 32 && state[j] & 2) || ((state[i] & 32) == 0 && (state[j] & 2) == 0)) {
        return false;
    }
    else return true;
}
 
void rotate(int gearNum, int way){
    if (way == 0) return;
    else if (way == 1) {
        int flag = state[gearNum] & 1;
        state[gearNum] = state[gearNum] >> 1;
        if (flag) state[gearNum] |= 128;
    } else {
        int flag = state[gearNum] & 128;
        state[gearNum] = state[gearNum] << 1;
        state[gearNum] &= ~256;
        if (flag) state[gearNum] |= 1;
    }
}
 
void getScore(){
    for (int i = 1; i <= 4; i++) {
        if (state[i] & 128) ans += int(pow(2, i-1));
    }
}
 
vector<int> getAction(int gear, int dir){
    vector<int> action(5);
    if (gear == 1) {
        action[1] = dir;
        if (isRevolve(1, 2)) action[2] = -action[1];
        if (isRevolve(2, 3)) action[3] = -action[2];
        if (isRevolve(3, 4)) action[4] = -action[3];
    } else if (gear == 2) {
        action[2] = dir;
        if (isRevolve(1, 2)) action[1] = -action[2];
        if (isRevolve(2, 3)) action[3] = -action[2];
        if (isRevolve(3, 4)) action[4] = -action[3];
    } else if (gear == 3) {
        action[3] = dir;
        if (isRevolve(2, 3)) action[2] = -action[3];
        if (isRevolve(3, 4)) action[4] = -action[3];
        if (isRevolve(1, 2)) action[1] = -action[2];
    } else {
        action[4] = dir;
        if (isRevolve(3, 4)) action[3] = -action[4];
        if (isRevolve(2, 3)) action[2] = -action[3];
        if (isRevolve(1, 2)) action[1] = -action[2];
    }
    return action;
}
 
void solve(int gear, int dir){
    vector<int> action = getAction(gear, dir);
    for (int i = 1; i <= 4; i++) rotate(i, action[i]);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    for (int i = 1; i <= 4; i++) {
        string s;
        cin >> s;
        for (int j = 7; j >= 0; j--) {
            int mul = int(pow(2, 7-j));
            int num = s[j]-'0';
            state[i] += num*mul;
        }
    }
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        int gear, dir;
        cin >> gear >> dir;
        solve(gear, dir);
    }
    getScore();
    cout << ans << '\n';
 
    return 0;
}

Reference

Graph