[백준 14891번] 톱니바퀴 C++

Andrew·2022년 1월 5일

C 삼성기출 코딩테스트

알고리즘연습

목록 보기

6/31

[14891번 톱니바퀴]
https://www.acmicpc.net/problem/14891

복잡한 알고리즘 없이 정직하게 조건대로 구현하는 문제였다. 코드 길이가 (헤더 제외) 약 2000byte 정도 나왔는데, 맞힌 사람 중에느 700 byte로 구현한 사람도 있었다. 좀 더 정진해야겠다.

풀이 방법

1.

톱니 바퀴를 2차원 배열로 1번~4번까지 모두 입력받는다.
움직이기 시작하는 톱니바퀴 번호와 방향을 K열을 가진 2차원 배열로 입력받는다.

2.

우선 spin 메서드를 구현한다. c++의 rotate라는 메서드를 이용했다. 방향이 -1일 때, 1차원 배열에서 보면 왼쪽으로 한 칸씩 이동하는 것과 같다. 반대로 1일 때는 오른쪽으로 한 칸씩 이동하는 것과 같다.

3.

checkEffect 메서드를 구현한다. 인접한 톱니바퀴 중 왼쪽에 위치한 톱니바퀴를 첫 번째 인자에, 오른쪽에 위치한 톱니바퀴를 두 번째 인자에 넣어주는 메서드를 구현한다. 왼쪽 톱니바퀴의 3번째 이빨과 오른쪽 톱니바퀴의 7번째 이빨의 값이 다르면 true를 반환한다.

4.

rippleEffect 메서드를 구현한다. switch문을 사용하여 1번 톱니바퀴에서 회전이 시작된다면 일어날 수 있는 경우의 수만큼 if문을 활용하여 각각의 결과를 구현한다.
여기서 주의할 점은 파급효과가 가장 멀리까지 뻗치고 돌아오면서, 멀리 있는 톱니바퀴부터 방향에 맞게 회전시켜 줘야한다(파급효과의 연속적 비교를 위해 이전의 톱니바퀴를 미리 회전시키면 안 된다).

5.

score 메서드는 마지막으로 점수를 계산해주는 메서드이다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int cogs[5][9];
int k;
int rotation[101][2];

bool checkEffect(int left, int right) {
	return cogs[left][3] != cogs[right][7];
}

int spin(int r, int dir) {
	if(dir == -1) {  // counter-clockwise
		rotate(cogs[r]+1, cogs[r] + 2 , cogs[r] + 9);
	} else if(dir == 1) {  // clockwise
		rotate(cogs[r]+1, cogs[r] + 8, cogs[r] + 9);
	}
	return 0;
}

void rippleEffect(int start, int d) {  // number of cogs

	switch(start) {
		case 1:
			if(checkEffect(1,2)) {  // first arg idx 3 vs. second arg idx 7
				if(checkEffect(2,3)) {
					if(checkEffect(3,4)) {
						spin(4,-d);
					}
					spin(3,d);
				}
				spin(2,-d);
			}
			spin(1,d);
			break;

		case 2:
			if(checkEffect(1,2) || checkEffect(2,3)) {
				if(checkEffect(1,2) && checkEffect(2,3)) {
					if(checkEffect(3,4)) {
						spin(4,d);
					}
					spin(3,-d);
					spin(1,-d);
				} else if(checkEffect(1,2)) {
					spin(1,-d);
				} else if(checkEffect(2,3)) {
					if(checkEffect(3,4)) {
						spin(4,d);
					}
					spin(3,-d);
				}
			}
			spin(2,d);
			break;

		case 3:
			if(checkEffect(2,3) || checkEffect(3,4)) {
				if(checkEffect(2,3) && checkEffect(3,4)) {
					if(checkEffect(1,2)) {
						spin(1,d);
					}
					spin(2,-d);
					spin(4,-d);
				} else if(checkEffect(2,3)) {
					if(checkEffect(1,2)) {
						spin(1,d);
					}
					spin(2,-d);
				} else if(checkEffect(3,4)) {
					spin(4,-d);
				}
			}
			spin(3,d);
			break;
		case 4:
			if(checkEffect(3,4)) {
				if(checkEffect(2,3)) {
					if(checkEffect(1,2)) {
						spin(1,-d);
					}
					spin(2,d);
				}
				spin(3,-d);
			}
			spin(4,d);
			break;
	}

	return;
}

void score() {
	for(int i=1;i<=4;++i) {
		switch(i) {
			case 1:
				if(cogs[i][1] == 1) {
					ans += 1;
				}
				break;
			case 2:
				if(cogs[i][1] == 1) {
					ans += 2;
				}
				break;
			case 3:
				if(cogs[i][1] == 1) {
					ans += 4;
				}
				break;
			case 4:
				if(cogs[i][1] == 1) {
					ans += 8;
				}
				break;
		}
	}

	return;
}

void sol() {
	for(int i=1;i<=k;++i) {
		rippleEffect(rotation[i][0], rotation[i][1]);
	}

	score();
	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	for(int i=1;i<=4;++i) {
		for(int j=1;j<=8;++j) {
			scanf("%1d", &cogs[i][j]);
		}
	}
	
	scanf("%d", &k);
	for(int i=1;i<=k;++i) {
		scanf("%d %d", &rotation[i][0], &rotation[i][1]);
	}

	sol();
	
	printf("%d\n", ans);
	
	return 0;
}