이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 46 번째 글 입니다.
목차
실버1 : 구현 문제이다.
생각
단순 구현 문제이다. 비트마스크 연습을 위해 비트마스크로 풀었다. 해당 과정을 하는 동안에 인접행렬 같은 matrix를 만들어 무언가를 해보려 했지만 좋지 못했다. 구현 문제는 노가다로 적어주는게 정신 건강에 이롭다.
Sudo-algorithm
- 입력을 받는다.
- 어떤 톱니바퀴를 돌리는 지 판단한다.
- 그 톱니바퀴를 돌렸을 때, 따라서 돌아가는 톱니바퀴의 방향을 정한다.
- 그 구한 톱니 바퀴의 방향대로 돌린다.
- 마지막에 답을 구한다.
특정 톱니바퀴를 돌렸을 때, 따라서 돌아가는 것의 숫자를 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;
}