백준 14891번 톱니바퀴 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14891

사용한 알고리즘: 구현


 4개의 톱니바퀴를 시계방향(1), 반시계방향(-1) 으로 돌릴때 해당 톱니바퀴의 양옆 톱니바퀴가 함께 돌아가는 문제입니다. 톱니바퀴는 총 8개의 돌기가 있고, 12시방향을 index 0 으로 시작하여 시계방향으로 index가 +1 됩니다. 모든 회전이 끝난 후 4개의 톱니바퀴의 각 12시 성분이 무엇인지 구하는 문제였습니다.

풀이과정은 다음과 같습니다.
(1) 톱니바퀴 i의 상태를 4x8 배열로 받고, 입력되는 톱니바퀴의 회전을 구현하는 함수 Turning 을 만들어 톱니바퀴 index i 와 회전방향을 구현합니다.

(2) 구현시 i톱니바퀴의 3시돌기의 극성( [i][2] )과 i+1톱니바퀴의 9시돌기의 극성( [i+1][6] )
i톱니바퀴의 9시돌기의 극성( [i][6] )과 i+1톱니바퀴의 3시돌기의 극성( [i-1][2] ) 를 비교하여 극성이 같을 경우 그 톱니바퀴도 다시 과정(1)의 함수로 넣어줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 0: 12시 , 2: 오른쪽, 6: 왼쪽
	int K, gear[4][8];
	bool visited[4];
	void Turning(int idx, int dir){
	if(idx<0||idx>3) return;
	if(visited[idx]) return;
	visited[idx] = true;
	bool rightside = false;
	bool leftside = false;
	if(idx+1<4&&gear[idx][2]!=gear[idx+1][6]) rightside = true;
	if(idx-1>=0&&gear[idx][6]!=gear[idx-1][2]) leftside = true;
	if(dir==1){
	int temp = gear[idx][7];
	for (int i = 7; i > 0; i--)
	gear[idx][i] = gear[idx][i-1];
	gear[idx][0] = temp;
	}
	else{
	int temp = gear[idx][0];
	for (int i = 0; i < 7; ++i)
	gear[idx][i] = gear[idx][i+1];
	gear[idx][7] = temp;
	}
	dir*=-1;
	if(rightside) Turning(idx+1,dir);
	if(leftside) Turning(idx-1,dir);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for (int i = 0; i < 4; ++i){
	int num;
	cin >> num;
	for (int j = 7; j >= 0; j--){
	gear[i][j] = num%10;
	num/=10;
	}
	}
	cin >> K;
	while(K--){
	int a, b;
	cin >> a >> b;
	memset(visited,false,sizeof(visited));
	Turning(a-1,b);
	}
	int ans = 0;
	for (int i = 0; i < 4; ++i)
	if(gear[i][0]==1)
	{
	ans+=pow(2,i);
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 14891.cpp hosted with ❤ by GitHub