Archive horanglab

백준 14891번 (톱니바퀴, C++, Simulation) / 추가 반례 [BAEKJOON]

#C# #C++ #구현·시뮬레이션

문제

https://www.acmicpc.net/problem/14891

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 29206 15688 11469 54.325%

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다.

또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다.

톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다.

톱니바퀴의 회전은 한 칸을 기준으로 한다.

회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다.

톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다.

톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.

예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다.

여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다.

2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다.

따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다.

4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다.

상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다.

다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다.

각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다.

방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

알고리즘 분류

출처

예제 입력 1

csharp 
10101111
01111101
11001110
00000010
2
3 -1
1 1

예제 출력 1

csharp 
7

예제 입력 2

csharp 
11111111
11111111
11111111
11111111
3
1 1
2 1
3 1

예제 출력 2

csharp 
15

예제 입력 3

csharp 
10001011
10000011
01011011
00111101
5
1 1
2 1
3 1
4 1
1 -1

예제 출력 3

csharp 
6

예제 입력 4

csharp 
10010011
01010011
11100011
01010101
8
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1

예제 출력 4

csharp 
5

추가 반례

예제 입력 A

csharp 
11111110
00000000
11111111
11111111
1
2 -1

예제 출력 A

csharp 
12

예제 입력 B

csharp 
11001110
10000101
01111110
01101111
4
2 -1
2 -1
2 1
2 1

예제 출력 B

csharp 
10

예제 입력 C

csharp 
01000100
00100010
01000100
00100010
2
2 -1
3 -1

예제 출력 C

csharp 
0

예제 입력 D

csharp 
01010101
10100010
11010101
00101010
6
3 -1
1 1
2 1
2 1
1 1
4 -1

예제 출력 D

csharp 
7

입력 확인 코드

톱니바퀴의 상태는 string 배열을 이용하여 구현

톱니바퀴의 회전은 List<int, int> 에 저장하여 처리할 예정

first : 톱니바퀴의 번호, second : 톱니바퀴가 회전하는 방향

1 -> 시계

-1 -> 반시계

cpp 
#include <iostream>
#include <list>

using namespace std;

// 톱니바퀴의 회전 횟수
int N, tempOne, tempTwo;

list<pair<int, int>> rotationList;
list<pair<int, int>>::iterator iter;

// 톱니 바퀴의 톱니
string cogWheel[4];

bool debug = true;

void DebugPrint()
{
	cout << "\n" << "입력받은 톱니바퀴의 상태" << "\n";
	for (int i = 0; i < 4; i++) {
		cout << cogWheel[i] << "\n";
	}
	cout << "\n" << "톱니바퀴의 회전" << "\n";
	for (iter = rotationList.begin(); iter != rotationList.end(); iter++) {
	cout << "iter->first : " << iter->first << " iter->second : " << iter->second  << "\n";
	}

}

void GetInput()
{
	for (int i = 0; i < 4; i++) {
		cin >> cogWheel[i];
	}
	cin >> N;

	// 톱니바퀴의 회전수 만큼 입력을 받습니다.
	while (N > 0) {
		cin >> tempOne >> tempTwo;
		rotationList.push_back(make_pair(tempOne, tempTwo));
		N--;
	}
}

int main()
{
	GetInput();
	if (debug) { DebugPrint(); }
	return 0;
}

톱니바퀴의 회전 구현

톱니바퀴는 String으로 구현되어 있다

톱니바퀴가 시계방향으로 회전할 경우 string의 마지막 인덱스를 0번 인덱스로 바꾸어주고 나머지는 인덱스 +1

톱니바퀴가 시계방향으로 회전할 경우 string의 마지막 인덱스를 7번 인덱스로 바꾸어주고 나머지는 인덱스 -1

cpp 
#include <iostream>
#include <list>

using namespace std;

// 톱니바퀴의 회전 횟수
int N, tempOne, tempTwo;

list<pair<int, int>> rotationList;
list<pair<int, int>>::iterator iter;

// 톱니 바퀴의 톱니
string cogWheel[4];

bool debug = true;

void DebugPrint()
{
	cout << "\n" << "회전 후 입력받은 톱니바퀴의 상태" << "\n";
	for (int i = 0; i < 4; i++) {
		cout << cogWheel[i] << "\n";
	}
}

void GetInput()
{
	for (int i = 0; i < 4; i++) {
		cin >> cogWheel[i];
	}
	cin >> N;

	// 톱니바퀴의 회전수 만큼 입력을 받습니다.
	while (N > 0) {
		cin >> tempOne >> tempTwo;
		rotationList.push_back(make_pair(tempOne, tempTwo));
		N--;
	}
}

void CogwheelRotation(int number, int dir)
{
	string tempString;
	// 톱니를 시계 방향으로 회전
	if (dir == 1) {
		tempString.push_back(cogWheel[number - 1][7]);
		for (int i = 0; i < 7; i++) {
			tempString.push_back(cogWheel[number - 1][i]);
		}
		if (debug) { cout << number << "번 톱니 " << "시계 방향 회전 : " << cogWheel[number - 1] << " -> "; }
		cogWheel[number - 1] = tempString;
		if (debug) { cout << tempString << "\n"; }
	}
	else { 	// 톱니를 반시계 방향으로 회전
		for (int i = 1; i < 8; i++) {
			tempString.push_back(cogWheel[number - 1][i]);
		}

		tempString.push_back(cogWheel[number - 1][0]);
		if (debug) { cout << number << "번 톱니 " << "반시계 방향 회전: "  << cogWheel[number - 1] << " -> "; }
		cogWheel[number - 1] = tempString;
		if (debug) { cout << tempString << "\n"; }
	}
}

int main()
{
	GetInput();
	for (iter = rotationList.begin(); iter != rotationList.end(); iter++) {
		CogwheelRotation(iter->first, iter->second);
	}
	if (debug) { DebugPrint(); }
	return 0;
}

톱니의 상호작용 구현

해당 톱니를 회전시킨 후

우측은 회전한 톱니의 2번 인덱스와 우측 톱니의 6번 인덱스를 비교 -> 극이 같다면 정지 / 다르다면 회전 방향과 반대로 회전

좌측은 회전한 톱니의 6번 인덱스와 우측 톱니의 2번 인덱스를 비교 -> 극이 같다면 정지 / 다르다면 회전 방향과 반대로 회전

cpp 
#include <iostream>
#include <list>
#include <cmath>

using namespace std;

// 톱니바퀴의 회전 횟수
int N, tempOne, tempTwo;

list<pair<int, int>> rotationList;
list<pair<int, int>>::iterator iter;

// 톱니 바퀴의 톱니
string cogWheel[4];

bool check[3];

bool debug = false;

int score = 0;

void DebugPrint()
{
	cout << "\n" << "톱니바퀴의 상태" << "\n";
	for (int i = 0; i < 4; i++) {
		cout << cogWheel[i] << "\n";
	}
	cout << "\n";
}

void GetInput()
{
	for (int i = 0; i < 4; i++) {
		cin >> cogWheel[i];
	}
	cin >> N;

	// 톱니바퀴의 회전수 만큼 입력을 받습니다.
	while (N > 0) {
		cin >> tempOne >> tempTwo;
		rotationList.push_back(make_pair(tempOne, tempTwo));
		N--;
	}
}

void CogwheelRotation(int number, int dir)
{
	string tempString;

	// 톱니를 시계 방향으로 회전
	if (dir == 1) {
		tempString.push_back(cogWheel[number - 1][7]);
		for (int i = 0; i < 7; i++) {
			tempString.push_back(cogWheel[number - 1][i]);
		}
		if (debug) { cout << number << "번 톱니 " << "시계 방향 회전 : " << cogWheel[number - 1] << " -> "; }
		cogWheel[number - 1] = tempString;
		if (debug) { cout << tempString << "\n"; }
	}
	else { 	// 톱니를 반시계 방향으로 회전
		for (int i = 1; i < 8; i++) {
			tempString.push_back(cogWheel[number - 1][i]);
		}

		tempString.push_back(cogWheel[number - 1][0]);
		if (debug) { cout << number << "번 톱니 " << "반시계 방향 회전: " << cogWheel[number - 1] << " -> "; }
		cogWheel[number - 1] = tempString;
		if (debug) { cout << tempString << "\n"; }
	}

}

void RotationCheck(int number, int dir)
{
	for (int i = 0; i < 3; i++) {
		cogWheel[i + 1][6] != cogWheel[i][2] ? check[i] = true : check[i] = false;
	}

	CogwheelRotation(number, dir);

	if (debug) { DebugPrint(); }
	if (debug) { cout << "상호작용 시작" << "\n"; }

	switch (number)
	{
		case 1:
			for (int i = 0; i < 3; i++) {
				if (check[i]) { CogwheelRotation(i + 2, dir * pow(-1, i + 1)); }
				else { break; }
			}

			break;

		case 2:
			for (int i = 1; i < 3; i++) {
				if (check[i]) {
					CogwheelRotation(i + 2, dir * pow(-1, i)); }
				else { break; }
			}

			if (check[0]) { CogwheelRotation(1, -dir); }
			break;

		case 3:
			for (int i = 1; i >= 0; i--) {
				if (check[i]) {
					CogwheelRotation(i + 1, dir * pow(-1, i));
				}
				else { break; }
			}
			if (check[2]) { CogwheelRotation(4, -dir); }
			break;

		case 4:
			for (int i = 2; i >= 0; i--) {
				if (check[i]) {
					CogwheelRotation(i + 1, dir * pow(-1, i + 1));
				}
				else { break; }
			}
			break;
	}
}

// 점수를 계산하는 함수
void ScoreCalculation()
{
	for (int i = 0; i < 4; i++) {
		if (cogWheel[i][0] == '1') { score += pow(2, i); }
	}
}

int main()
{
	GetInput();
	for (iter = rotationList.begin(); iter != rotationList.end(); iter++) {
		RotationCheck(iter->first, iter->second);
		if (debug) { DebugPrint(); }
	}

	ScoreCalculation();

	if (debug) { DebugPrint(); }

	cout << score;

	return 0;
}

로직 오류

코드를 작성하면서 문제를 다시 살펴보는데 구현이 틀렸다.

톱니가 회전한 후에 만나는 톱니의 극을 비교하는 것이 아닌 회전하기 전에 미리 회전시킬 톱니를 체크를 해야 한다.

예제 3번 디버깅

plaintext 
10001011
10000011
01011011
00111101
5
1 1
2 1
3 1
4 1
1 -1

문제의 톱니바퀴 회전
1번 톱니 시계 방향 회전 : 10001011 -> 11000101

톱니바퀴의 상태
11000101
10000011
01011011
00111101

상호작용 시작
2번 톱니 반시계 방향 회전: 10000011 -> 00000111
3번 톱니 시계 방향 회전 : 01011011 -> 10101101

톱니바퀴의 상태
11000101
00000111
10101101
00111101

문제의 톱니바퀴 회전
2번 톱니 시계 방향 회전 : 00000111 -> 10000011

톱니바퀴의 상태
11000101
10000011
10101101
00111101

상호작용 시작
1번 톱니 반시계 방향 회전: 11000101 -> 10001011

톱니바퀴의 상태
10001011
10000011
10101101
00111101

문제의 톱니바퀴 회전
3번 톱니 시계 방향 회전 : 10101101 -> 11010110

톱니바퀴의 상태
10001011
10000011
11010110
00111101

상호작용 시작
4번 톱니 반시계 방향 회전: 00111101 -> 01111010

톱니바퀴의 상태
10001011
10000011
11010110
01111010

문제의 톱니바퀴 회전
4번 톱니 시계 방향 회전 : 01111010 -> 00111101

톱니바퀴의 상태
10001011
10000011
11010110
00111101

상호작용 시작
3번 톱니 반시계 방향 회전: 11010110 -> 10101101
2번 톱니 시계 방향 회전 : 10000011 -> 11000001
1번 톱니 반시계 방향 회전: 10001011 -> 00010111

톱니바퀴의 상태
00010111
11000001
10101101
00111101

문제의 톱니바퀴 회전
1번 톱니 반시계 방향 회전: 00010111 -> 00101110

톱니바퀴의 상태
00101110
11000001
10101101
00111101

상호작용 시작

톱니바퀴의 상태
00101110
11000001
10101101
00111101

톱니바퀴의 상태
00101110
11000001
10101101
00111101

답 : 6

예제 4번 디버깅

plaintext 
10010011
01010011
11100011
01010101
8
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1

문제의 톱니바퀴 회전
1번 톱니 시계 방향 회전 : 10010011 -> 11001001

톱니바퀴의 상태
11001001
01010011
11100011
01010101

상호작용 시작
2번 톱니 반시계 방향 회전: 01010011 -> 10100110
3번 톱니 시계 방향 회전 : 11100011 -> 11110001
4번 톱니 반시계 방향 회전: 01010101 -> 10101010

톱니바퀴의 상태
11001001
10100110
11110001
10101010

문제의 톱니바퀴 회전
2번 톱니 시계 방향 회전 : 10100110 -> 01010011

톱니바퀴의 상태
11001001
01010011
11110001
10101010

상호작용 시작
3번 톱니 반시계 방향 회전: 11110001 -> 11100011
1번 톱니 반시계 방향 회전: 11001001 -> 10010011

톱니바퀴의 상태
10010011
01010011
11100011
10101010

문제의 톱니바퀴 회전
3번 톱니 시계 방향 회전 : 11100011 -> 11110001

톱니바퀴의 상태
10010011
01010011
11110001
10101010

상호작용 시작
2번 톱니 반시계 방향 회전: 01010011 -> 10100110
1번 톱니 시계 방향 회전 : 10010011 -> 11001001

톱니바퀴의 상태
11001001
10100110
11110001
10101010

문제의 톱니바퀴 회전
4번 톱니 시계 방향 회전 : 10101010 -> 01010101

톱니바퀴의 상태
11001001
10100110
11110001
01010101

상호작용 시작

톱니바퀴의 상태
11001001
10100110
11110001
01010101

문제의 톱니바퀴 회전
1번 톱니 반시계 방향 회전: 11001001 -> 10010011

톱니바퀴의 상태
10010011
10100110
11110001
01010101

상호작용 시작
2번 톱니 시계 방향 회전 : 10100110 -> 01010011
3번 톱니 반시계 방향 회전: 11110001 -> 11100011
4번 톱니 시계 방향 회전 : 01010101 -> 10101010

톱니바퀴의 상태
10010011
01010011
11100011
10101010

문제의 톱니바퀴 회전
2번 톱니 반시계 방향 회전: 01010011 -> 10100110

톱니바퀴의 상태
10010011
10100110
11100011
10101010

상호작용 시작
3번 톱니 시계 방향 회전 : 11100011 -> 11110001
1번 톱니 시계 방향 회전 : 10010011 -> 11001001

톱니바퀴의 상태
11001001
10100110
11110001
10101010

문제의 톱니바퀴 회전
3번 톱니 반시계 방향 회전: 11110001 -> 11100011

톱니바퀴의 상태
11001001
10100110
11100011
10101010

상호작용 시작
2번 톱니 시계 방향 회전 : 10100110 -> 01010011
1번 톱니 반시계 방향 회전: 11001001 -> 10010011

톱니바퀴의 상태
10010011
01010011
11100011
10101010

문제의 톱니바퀴 회전
4번 톱니 반시계 방향 회전: 10101010 -> 01010101

톱니바퀴의 상태
10010011
01010011
11100011
01010101

상호작용 시작

톱니바퀴의 상태
10010011
01010011
11100011
01010101

톱니바퀴의 상태
10010011
01010011
11100011
01010101

답 : 5

통과된 코드

cpp 
#include <iostream>
#include <list>
#include <cmath>

using namespace std;

// 톱니바퀴의 회전 횟수
int N, tempOne, tempTwo;

list<pair<int, int>> rotationList;
list<pair<int, int>>::iterator iter;

// 톱니 바퀴의 톱니
string cogWheel[4];

// 회전할 톱니체크에 필요
bool check[3];

bool debug = false;

// 결과
int score = 0;

// 디버그용 함수
void DebugPrint()
{
	cout << "\n" << "톱니바퀴의 상태\n";
	for (int i = 0; i < 4; i++) {
		cout << cogWheel[i] << "\n";
	}
}

// 문제의 입력을 받는 함수
void GetInput()
{
	for (int i = 0; i < 4; i++) {
		cin >> cogWheel[i];
	}
	cin >> N;

	// 톱니바퀴의 회전수 만큼 입력을 받습니다.
	while (N > 0) {
		cin >> tempOne >> tempTwo;
		rotationList.push_back(make_pair(tempOne, tempTwo));
		N--;
	}
}

// 톱니를 회전하는 함수
void CogwheelRotation(int number, int dir)
{
	string tempString;

	// 톱니를 시계 방향으로 회전
	if (dir == 1) {
		tempString.push_back(cogWheel[number - 1][7]);
		for (int i = 0; i < 7; i++) {
			tempString.push_back(cogWheel[number - 1][i]);
		}
		if (debug) { cout << number << "번 톱니 " << "시계 방향 회전 : " << cogWheel[number - 1] << " -> "; }
		cogWheel[number - 1] = tempString;
		if (debug) { cout << tempString << "\n"; }
	}
	else { 	// 톱니를 반시계 방향으로 회전
		for (int i = 1; i < 8; i++) {
			tempString.push_back(cogWheel[number - 1][i]);
		}

		tempString.push_back(cogWheel[number - 1][0]);
		if (debug) { cout << number << "번 톱니 " << "반시계 방향 회전: " << cogWheel[number - 1] << " -> "; }
		cogWheel[number - 1] = tempString;
		if (debug) { cout << tempString << "\n"; }
	}

}

// 회전할 톱니를 체크
void RotationCheck(int number, int dir)
{

	for (int i = 0; i < 3; i++) {
		cogWheel[i + 1][6] != cogWheel[i][2] ? check[i] = true : check[i] = false;
	}
	if (debug) { cout << "\n" << "문제의 톱니바퀴 회전" << "\n"; }

	CogwheelRotation(number, dir);

	if (debug) { DebugPrint(); }
	if (debug) { cout << "\n" << "상호작용 시작" << "\n"; }

	switch (number)
	{
		case 1: // 2번부터 4번
			for (int i = 0; i < 3; i++) {
				if (check[i]) { CogwheelRotation(i + 2, dir * pow(-1, i + 1)); }
				else { break; }
			}
			break;

		case 2: //3번부터 4번
			for (int i = 1; i < 3; i++) {
				if (check[i]) {
					CogwheelRotation(i + 2, dir * pow(-1, i)); }
				else { break; }
			}

			// 1번
			if (check[0]) { CogwheelRotation(1, -dir); }
			break;

		case 3: // 2번부터 1번
			for (int i = 1; i >= 0; i--) {
				if (check[i]) {
					CogwheelRotation(i + 1, dir * pow(-1, i));
				}
				else { break; }
			}

			// 4번
			if (check[2]) { CogwheelRotation(4, -dir); }
			break;

		case 4: // 3번부터 1번
			for (int i = 2; i >= 0; i--) {
				if (check[i]) {
					CogwheelRotation(i + 1, dir * pow(-1, i + 1));
				}
				else { break; }
			}
			break;
	}
}

// 점수를 계산하는 함수
void ScoreCalculation()
{
	for (int i = 0; i < 4; i++) {
		if (cogWheel[i][0] == '1') { score += pow(2, i); }
	}
}

int main()
{
	GetInput();

	for (iter = rotationList.begin(); iter != rotationList.end(); iter++) {
		RotationCheck(iter->first, iter->second);
		if (debug) { 
			DebugPrint(); 
		}
	}

	// 점수 계산
	ScoreCalculation();

	if (debug) { 
		DebugPrint(); 
		cout << "\n답 : ";
	}

	cout << score;

	return 0;
}

중간에 디버깅 코드를 작성하고 제출할 때 제외하는 것을 잊어서 계속 틀렸다.