[BOJ] 백준 14891 톱니바퀴 간단한설명과 코드 C++

15 Jan 2020

Reading time ~2 minutes

문제 정보

백준 ( BOJ ) 14891 톱니바퀴

문제 풀이 : 시뮬레이션

문제 출처 : https://www.acmicpc.net/problem/14891

시작 Thinking

문제 풀이

우선 이 문제는 여러 풀이 방법이 있곘지만, 전 그중 하나에 대해

알려드리도록 하겠습니다.

우선 톱니바퀴는 4개이며, 이 4개를 연관지어 생각하려면

클래스를 만들어서 각각의 톱니바퀴들을 이어주거나,

배열로 묶어서 생각하면 편하실 겁니다.

저는 배열[4][8] 로 만들었고,

배열[n][2] != [n+1][6]

으로 판단해 돌아갈지 안돌아 갈지 정하였습니다.

그리고 가장 중요한건, 톱니바퀴를 어떻게 탐색 할 것인가인데요,

저는 재귀함수를 사용하여 만들었습니다.

fun ( lr, way, n ) {
  if(lr == 1) // 오른쪽 탐색중일시, 
    fun(lr,way*-1,n+1)
    stack. push(make_pair(n, way*-1)
}

간단하게 보면 이런식으로 진행을 하였습니다.

재귀를 돌면서, 바꿔야 할 톱니들을 저장해놓고

한번에 끝나고 바꿔야 중간에 결과가 바뀌지 않아요.

코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int k;
vector<vector<int>> chain(4, vector<int>(8, 0));
stack<pair<int, int>> willBeChanged;
void roll(int way, int n){
	int temp;
	if (way == -1) {
		temp = chain[n][0];
		for (int i = 0; i < 7; i++) {
			chain[n][i] = chain[n][i + 1];
		}
		chain[n][7] = temp;
	}
	if (way == 1) {
		temp = chain[n][7];
		for (int i = 7; i > 0; i--) {
			chain[n][i] = chain[n][i - 1];
		}
		chain[n][0] = temp;
	}
}
void fun(int lr, int way, int n) {
	int tempWay, tempN;
	if (n >= 0 && n < 4) {
		if ( lr == -1 && ( chain[n][2] != chain[n + 1][6] )) {
			fun(-1, way*-1, n - 1);
			willBeChanged.push(make_pair(way*-1, n));
		}
		else if (lr == 1 && (chain[n - 1][2] != chain[n][6])) {
			fun(1, way*-1, n + 1);
			willBeChanged.push(make_pair(way*-1, n));
		}
	}
}
int main() {
	
	int temp;
	int tempN;
	int tempWay;
	int ta, tb;
	for (int i = 0; i < 4; i++) {
		cin >> temp;
		chain[i][0] = temp / 10000000;
		chain[i][1] = (temp / 1000000) % 10;
		chain[i][2] = (temp / 100000) % 10;
		chain[i][3] = (temp / 10000) % 10;
		chain[i][4] = (temp / 1000) % 10;
		chain[i][5] = (temp / 100) % 10;
		chain[i][6] = (temp /10) % 10;
		chain[i][7] = temp % 10;
	}
	cin >> k;

	for (int i = 0; i < k; i++) {
		cin >> tempN >> tempWay;
		tempN--;
		fun(-1, tempWay, tempN - 1);
		fun(1, tempWay, tempN + 1);
		while (!willBeChanged.empty()) {
			ta = willBeChanged.top().first;
			tb = willBeChanged.top().second;
			willBeChanged.pop();
			roll(ta, tb);
		}
		roll(tempWay, tempN);
	}
	
	cout << chain[0][0] * 1 + chain[1][0] * 2 + chain[2][0] * 4 + chain[3][0] * 8;
	cin >> temp;
	return 0;
}

문제 후기

소요 시간 : 46분

틀린 횟수 : 0 번

발생 에러 : 없음

백준 C++시뮬레이션