백준 14891번 : 톱니바퀴

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

풀이에 참조한 링크 :

  * 벡터의 insert, erase - hsdevelopment.tistory.com/164

  * 반례 - www.acmicpc.net/board/view/50149

내 풀이(2021.1.3.) : 

#include <iostream>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

vector<int> wheel[5];

void clockwise(int num) {
	vector<int>& v = wheel[num];
	int temp = v.back();
	v.pop_back();
	v.insert(v.begin(), temp);
}

void counterclockwise(int num) {
	vector<int>& v = wheel[num];
	int temp = v.front();
	v.erase(v.begin());
	v.push_back(temp);
}

void rotate(int num, int direction) {
	if (direction == 1) clockwise(num);
	else counterclockwise(num);
	/* debug
	for (int i = 0; i < 4; i++) {
		cout << "WHEEL" << i + 1 << " : ";
		for (int j = 0; j < 8; j++) {
			cout << wheel[i + 1][j];
		}
		cout << endl;
	}
	cout << endl;
	*/
}

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

	for (int i = 0; i < 4; i++) {
		string line; getline(cin, line);
		for (int j = 0; j < 8; j++) {
			wheel[i + 1].push_back(line[j] - '0');
		}
	}

	int K; cin >> K;
	for (int i = 0; i < K; i++) {
		int num, dir;
		cin >> num >> dir;

		int direction[5]; // rotation direction
		bool check[5] = { false, }; // whether rotate or not

		// set direction
		if (num % 2 == 1) {
			int temp = dir;
			for (int j = 1; j < 5; j++) {
				direction[j] = temp;
				temp *= -1;
			}
		}
		else {
			int temp = -dir;
			for (int j = 1; j < 5; j++) {
				direction[j] = temp;
				temp *= -1;
			}
		}

		// rotate self unconditionally
		check[num] = true;

		// propogate right
		int num_right = num;
		while (num_right < 4) {
			if (wheel[num_right].at(2) != wheel[num_right + 1].at(6)) {
				check[++num_right] = true; 
			}
			else break;
		}

		// propogate left
		int num_left = num;
		while (num_left > 1) {
			if (wheel[num_left].at(6) != wheel[num_left - 1].at(2)) {
				check[--num_left] = true;
			}
			else break;
		}

		// execute actual rotation
		for (int i = 1; i < 5; i++) {
			if (check[i] == true) {
				rotate(i, direction[i]); 
			}
		}
	}

	// calculate sum
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		sum += wheel[i + 1].at(0) * (int)pow(2, i);
	}
	cout << sum;

	return 0;
}

Visual Studio에서는 math.h 파일을 include하지 않아도 pow함수를 사용할 수 있지만

백준 환경에서는 include 하지 않으면 컴파일 오류가 난다.

pow함수는 원래 math.h 파일에 선언된 함수이다.

 

같은 극인지 다른 극인지에 대한 판단을

연쇄적인 시점에서 하는 것이 아니라

초기 상태에서만 하는 것임을

문제로부터 명확하게 이해하지 못해서 헷갈렸다.

 

양 끝의 값을 삽입 · 삭제하므로, deque를 이용하면 편리하다.