[구현] 톱니바퀴 14891

톱니바퀴 14891

문제의 이해.

- 8개의 톱니를 가진 4개의 톱니바퀴 존재. 톱니는 N 혹은 S극

- 맞닿은 톱니의 극이 만약,

1. 같다면 : 회전하지 않는다.

2. 다르다면 : 반대방향으로 회전한다. ( 회전시킨 톱니바퀴가 시계 방향으로 돌았으면 맞물린 톱니바퀴는 반시계방향으로 회전)

주의사항.

- 출력 시, 문제에 나온대로 톱니바퀴의 점수의 합을 계산해야한다.

 

 

풀이코드 ( 망한 스파게티 코드 )

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;
// 14891 톱니바퀴



vector<vector<int>> saw(4, vector<int>(8));
int k; // 회전 횟수
vector<int> r(1000); // 회전시킨 톱니바퀴의 번호
vector<int> dir(1000); // 회전 방향
bool isRotated[4];

void push(vector<int>& vec, int index, int flag){
	// 회전시켰다면 return
	if(isRotated[index]) return;
	
	// 시계 방향 
	if(flag == 1){
		int end = vec.back();
		for(int i = 0; i < vec.size() - 1; i++){
			vec[i + 1] = vec[i];
		}
		vec[0] = end;
	}
	
	// 반시계
	else if(flag == -1){
		int start = vec.front();
		for(int i = 0; i < vec.size() - 1; i++){
			vec[i] = vec[i + 1];
		}
		vec[vec.size() - 1] = start;
	}
	isRotated[index] = true;
	
	printf(" %s 방향으로 회전시킨 %d 번째 톱니바퀴\n", (flag == 1)? "시계" : "반시계", index);
}

// rotate(몇번째 회전인지, 현재 몇 번째 톱니바퀴에 있는지, 어느 방향 회전인지)
void rotate(int count, int now, int direction){
	// 범위 체크
	if(now < 0 || now >= 4) return;
	// 다 돌렷으면 끝
	bool ok = true;
	for(int i = 0; i < 4; i++){
		if(!isRotated[i]) ok = false;
	}
	if(ok) return;
	
	if(!ok && count > 4) return;
	
	

	// 왼쪽
	int left = now - 1;
	bool leftOK = true;
	if(left >=0 && left < 4){
		// 극이 다르다면
		if(saw[left][2] != saw[now][6]){
			push(saw[left], left, direction * -1);
		}
		// 극이 같다면
		else{
			isRotated[left] = true;
			leftOK = false;
		}
	}
		
	
	// 오른쪽
	int right = now + 1;
	bool rightOK = true;
	if(right >= 0 && right < 4){
		// 극이 다르다면
		if(saw[right][6] != saw[now][2]){
			push(saw[right], right, direction * -1);
		}
		// 극이 같다면
		else{
			isRotated[right] = true;
			rightOK = false;
		}
	}
	
	push(saw[now], now, direction);
	
	if(leftOK) rotate(count + 1, left, direction * -1);
	if(rightOK) rotate(count + 1, right, direction * -1);

	return;
}

int main(){
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 8; j++){
			scanf("%1d",&saw[i][j]); 
		}
	}
	cin >> k;
	
	for(int i = 0 ; i < k ; i++){
		cin >> r[i] >> dir[i];
		r[i] -= 1;
	}
	
	for(int i = 0; i < k; i++){
		fill_n(isRotated, 4, false);
		rotate(1, r[i], dir[i]);
		cout << "\n";
	}
		
		
	int ans = 0;
	for(int i = 0; i < 4; i++){
		if(saw[i][0] == 1){
			ans += pow(2, i);
		}
	}
	cout << ans << '\n';
	
	
	
	}

노트에서 명확히 생각해야 한다고 항상 되뇌이면서도, 아이디어가 번뜩이면 바로 코딩에 돌입하는 것이 문제이다.

내가 떠올린 아이디어가, 문제의 조건은 어긋나지 않는지, 논리를 그대로 따라가서 코딩하면 바로 예제가 나오는지 이런 것들을 명확히 보고 돌입해야한다.

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cmath>
using namespace std;
// 14891 톱니바퀴



vector<vector<int>> saw(4, vector<int>(8));
int k; // 회전 횟수
vector<int> r(1000); // 회전시킨 톱니바퀴의 번호
vector<int> dir(1000); // 회전 방향
bool isRotated[4];

void push(vector<int>& vec, int flag){
	if(flag == 0) return;
	
	// 시계 방향 
	if(flag == 1){
		int end = vec.back();
		for(int i = vec.size() - 1; i > 0; i--){
			vec[i] = vec[i - 1];
		}
		vec[0] = end;
	}
	
	// 반시계
	else if(flag == -1){
		int start = vec.front();
		for(int i = 0; i < vec.size() - 1; i++){
			vec[i] = vec[i + 1];
		}
		vec[vec.size() - 1] = start;
	}
}

int main(){
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 8; j++){
			scanf("%1d",&saw[i][j]); 
		}
	}
	cin >> k;
	
	for(int i = 0 ; i < k ; i++){
		cin >> r[i] >> dir[i];
		r[i] -= 1;
	}
	

	// 회전시키기
	for(int rotate = 0; rotate < k; rotate++){
		int criteria = r[rotate];
		int direction = dir[rotate];
		
		// flags[i] 가 0이면 무회전, 1이면 시계, -1이면 반시계
		vector<int> flags(4, 0);
		flags[criteria] = direction;
		
		// 왼쪽
		for(int left = criteria - 1; left >= 0; left--){
			// 극이 같지 않으면 시계 반시계 결정
			if(saw[left][2] != saw[left + 1][6]) 
				flags[left] = -flags[left + 1];			
				
			else{
				break;
			}	
				
			
		}
		
		// 오른쪽
		for(int right = criteria + 1; right < 4; right++){
			// 극이 같지 않으면 시계 반시계 결정
			if(saw[right - 1][2] != saw[right][6]) 
				flags[right] = -flags[right - 1];			
				
			else{
				break;
			}	
		}
		
		for(int i = 0; i < 4 ; i++){
			push(saw[i], flags[i]);
		}
	}
	
	
		
	int ans = 0;
	for(int i = 0; i < 4; i++){
		if(saw[i][0] == 1){
			ans += pow(2, i);
		}
	}
	cout << ans << '\n';
	
	
	
	}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

0. 입출력에 주의하자.

- 각 톱니바퀴의 극이 01001011 이런식으로 붙여져있으므로, string 으로 받든지, scanf("%1d) 로 받아야한다. 무지성으로 cin 으로 받으면 알 수 없는 틀렸습니다 지옥에 빠질 수 있다.

1. 누굴 먼저 돌려야할까?

- 기준이 되는 톱니바퀴 ? 바로 왼쪽 ? 바로 오른쪽 ? 모두 아니다. 문제에서 톱니바퀴의 회전은 동시에 일어난다. 하지만, 반복문을 돌리면서 한다면, 누군가는 먼저 돌아가기 때문에 극이 바뀌는 상황이 발생되어 틀린 답이 나오고 만다.

- 시뮬레이션 문제에서 흔히 보이는 상황인데, 이럴 때는 각 톱니바퀴가 어디로 회전할지 미리 조사 해둔 뒤에, 회전을 한다. 그러면 동시에 회전을 하는 효과를 볼 수 있는 것이다. 59번 라인의 flags 벡터가 이 조사를 저장해둔다.

2. 기준점의 왼쪽과 오른쪽 (톱니의 극이 12시부터 저장되어 있는 것에 유의하자.)

- 기준점 - 1 부터 0까지 조사.

- 기준점 + 1 부터 3 까지 조사.

3. 톱니를 회전시킬 때의 방향

- 반시계일 때와 시계 방향일때 어떻게 배열을 밀어야하는지 생각해보자.

3. 답 도출

- 문제의 output 을 보면, i(i = 0, 1, 2, 3) 번째 톱니일 때 12시 방향의 극이 1이라면 pow(2, i) 를 더해준 합을 출력해준다. 이에 착안하여 답을 도출하자.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 시계 반시계 방향 push 함수 17라인 을 구현할 때, 너무 쉽게 생각한 나머지 시계방향을 매우 멍청하게 구현하여 예제 답조차 나오지 않는 상황이 있었다. 아무리 쉬워보여도 한번 적어보고 구현하자.