백준 9019번

DSLR

Posted by ChoiCube84 on August 05, 2023 · 28 mins read
프로그래밍 문제풀이

백준 9019번

오늘 풀어본 문제는 백준의 9019번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 3

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 $0$ 이상 $10,000$ 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. $n$의 네 자릿수를 $d_1$, $d_2$, $d_3$, $d_4$라고 하자(즉 $n = ((d_1 \times 10 + d_2) \times 10 + d_3) \times 10 + d_4$라고 하자)

  1. D: D 는 $n$을 두 배로 바꾼다. 결과 값이 $9999$ 보다 큰 경우에는 $10000$ 으로 나눈 나머지를 취한다. 그 결과 값$(2n \mod 10000)$을 레지스터에 저장한다.

  2. S: S 는 $n$에서 $1$ 을 뺀 결과 $n-1$을 레지스터에 저장한다. $n$이 $0$ 이라면 $9999$ 가 대신 레지스터에 저장된다.

  3. L: L 은 $n$의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 $d_2$, $d_3$, $d_4$, $d_1$이 된다.

  4. R: R 은 $n$의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 $d_4$, $d_1$, $d_2$, $d_3$이 된다. 위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 $n = 1234$ 라면 여기에 L 을 적용하면 $2341$ 이 되고 R 을 적용하면 $4123$ 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 $A$와 $B$ $(A \neq B)$에 대하여 $A$를 $B$로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 $A = 1234$, $B = 3412$ 라면 다음과 같이 두 개의 명령어를 적용하면 $A$를 $B$로 변환할 수 있다.

$1234 \to_L 2341 \to_L 3412$
$1234 \to_R 4123 \to_R 3412$

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

$n$의 자릿수로 $0$ 이 포함된 경우에 주의해야 한다. 예를 들어서 $1000$ 에 L 을 적용하면 $0001$ 이 되므로 결과는 $1$ 이 된다. 그러나 R 을 적용하면 $0100$ 이 되므로 결과는 $100$ 이 된다.

입력

프로그램 입력은 $T$ 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 $T$ 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 $A$와 $B$ $(A \neq B)$가 공백으로 분리되어 차례로 주어지는데 $A$는 레지스터의 초기 값을 나타내고 $B$는 최종 값을 나타낸다. $A$ 와 $B$ 는 모두 $0$ 이상 $10,000$ 미만이다.

출력

$A$에서 $B$로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

풀이과정

처음 문제를 읽어봤을 때, 한 번에 명령어 나열을 알아내는 것은 힘들어 보였고, ‘최소’ 길이의 명령어 나열을 해야된다는 조건을 고려했을 때, BFS를 활용하여 문제를 풀 수 있을 것이라는 생각이 들었다. 현재 숫자와 거쳐온 명령어들을 함꼐 저장하도록 std::pair 을 이용하여 정보를 묶고, std::queue 를 이용하여 저장하도록 하였다.

첫 번째 시도

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

pair<int, string> D(pair<int, string> initialValue);
pair<int, string> S(pair<int, string> initialValue);
pair<int, string> L(pair<int, string> initialValue);
pair<int, string> R(pair<int, string> initialValue);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfTestCases, initialValue, finalValue;
	string result;

	queue<pair<int, string>> converted;

	cin >> numberOfTestCases;

	while (numberOfTestCases--) {
		cin >> initialValue >> finalValue;

		converted.push({ initialValue, "" });

		while (true) {
			pair<int, string> currentStatus = converted.front();
			converted.pop();

			if (currentStatus.first == finalValue) {
				result = currentStatus.second;
				break;
			}
			else {
				converted.push(D(currentStatus));
				converted.push(S(currentStatus));
				converted.push(L(currentStatus));
				converted.push(R(currentStatus));
			}
		}

		cout << result << "\n";

		while (!converted.empty()) {
			converted.pop();
		}
	}

	return 0;
}

pair<int, string> D(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first * 2) % 10000;
	converted.second = initialValue.second + "D";

	return converted;
}

pair<int, string> S(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first + 9999) % 10000;
	converted.second = initialValue.second + "S";

	return converted;
}

pair<int, string> L(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 1000) * 10 + (initialValue.first / 1000);
	converted.second = initialValue.second + "L";

	return converted;
}

pair<int, string> R(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 10) * 1000 + (initialValue.first / 10);
	converted.second = initialValue.second + "R";

	return converted;
}

실행 결과는 메모리 초과였다.

두 번째 시도

메모리 초과가 발생했다는 것은, 말 그대로 사용할 수 있는 저장 공간보다 많은 공간을 사용하려고 했다는 의미이다. 이를 해결하기 위해서는 중복된 정보를 제거하는 것이 필요하다고 생각했다.

중복된 정보가 뭐가 있을지를 생각해본 결과, 같은 숫자에 도달하는 다른 방식이 있을 수 있음을 떠올렸다. 예를 들어, $1010$ 에서 $0101$ 을 만드는 방법이 L 명령어를 사용하는 것도 가능하지만, R 명령어를 사용하는 것이 가능하다. 이러한 경우가 큐에 모두 들어가게 되면, 이후에 이미 확인한 수를 다시 확인하게 되는 경우가 늘어나게 된다.

visted 변수를 추가하여 각 숫자에 대하여 확인했는지 정보를 저장하도록 코드를 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

pair<int, string> D(pair<int, string> initialValue);
pair<int, string> S(pair<int, string> initialValue);
pair<int, string> L(pair<int, string> initialValue);
pair<int, string> R(pair<int, string> initialValue);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfTestCases, initialValue, finalValue;
	string result;
	bool visited[10001] = { 0, };

	queue<pair<int, string>> converted;

	cin >> numberOfTestCases;

	while (numberOfTestCases--) {
		cin >> initialValue >> finalValue;

		converted.push({ initialValue, "" });

		while (true) {
			pair<int, string> currentStatus = converted.front();
			converted.pop();

			if (visited[currentStatus.first]) {
				break;
			}
			else {
				visited[currentStatus.first] = true;

				if (currentStatus.first == finalValue) {
					result = currentStatus.second;
					break;
				}
				else {
					converted.push(D(currentStatus));
					converted.push(S(currentStatus));
					converted.push(L(currentStatus));
					converted.push(R(currentStatus));
				}
			}
		}

		cout << result << "\n";

		while (!converted.empty()) {
			converted.pop();
		}
	}

	return 0;
}

pair<int, string> D(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first * 2) % 10000;
	converted.second = initialValue.second + "D";

	return converted;
}

pair<int, string> S(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first + 9999) % 10000;
	converted.second = initialValue.second + "S";

	return converted;
}

pair<int, string> L(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 1000) * 10 + (initialValue.first / 1000);
	converted.second = initialValue.second + "L";

	return converted;
}

pair<int, string> R(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 10) * 1000 + (initialValue.first / 10);
	converted.second = initialValue.second + "R";

	return converted;
}

실행 결과 실패하고 말았다.

세 번째 시도

실패의 원인을 한참 찾아본 결과, 테스트 케이스마다 visted 변수를 제대로 초기화해주지 않아 문제가 발생한 것이 원인이었다. 이를 수정한 코드는 다음과 같다.

#include <bits/stdc++.h>

using namespace std;

pair<int, string> D(pair<int, string> initialValue);
pair<int, string> S(pair<int, string> initialValue);
pair<int, string> L(pair<int, string> initialValue);
pair<int, string> R(pair<int, string> initialValue);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfTestCases, initialValue, finalValue;
	string result = "";
	bool visited[10000] = { false, };

	queue<pair<int, string>> converted;

	cin >> numberOfTestCases;

	while (numberOfTestCases--) {
		cin >> initialValue >> finalValue;

		converted.push({ initialValue, "" });

		while (true) {
			pair<int, string> currentStatus = converted.front();
			converted.pop();

			if (visited[currentStatus.first] == true) {
				continue;
			}
			else {
				visited[currentStatus.first] = true;

				if (currentStatus.first == finalValue) {
					result = currentStatus.second;
					break;
				}
				else {
					converted.push(D(currentStatus));
					converted.push(S(currentStatus));
					converted.push(L(currentStatus));
					converted.push(R(currentStatus));
				}
			}
		}

		cout << result << "\n";

		while (!converted.empty()) {
			converted.pop();
		}

		for (int i = 0; i < 10000; i++) {
			visited[i] = false;
		}
	}

	return 0;
}

pair<int, string> D(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first * 2) % 10000;
	converted.second = initialValue.second + "D";

	return converted;
}

pair<int, string> S(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first + 9999) % 10000;
	converted.second = initialValue.second + "S";

	return converted;
}

pair<int, string> L(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 1000) * 10 + (initialValue.first / 1000);
	converted.second = initialValue.second + "L";

	return converted;
}

pair<int, string> R(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 10) * 1000 + (initialValue.first / 10);
	converted.second = initialValue.second + "R";

	return converted;
}

실행 결과, 시간 초과가 발생하였고, 이후의 제출에서도 계속 시간 초과가 발생하였다.

6번째 시도

시간 초과의 원인을 계속 찾아 헤멘 결과, std::string 을 더해서 저장하는 과정에서 시간이 너무 오래걸리는 것으로 판명되었다.

처음 숫자에서 어떤 숫자로 오기까지의 전체 명령어를 저장하는 대신, 지난 번 숫자에서 넘어오기 위한 명령어 한 개만 저장하고, history 라는 변수를 만들어 거꾸로 숫자를 추적해 올라갈 수 있도록 저장해두었다.

마지막으로 출력하는 과정에서는 history 변수를 활용하여 결과 문자열을 만들고, 이를 뒤집어 출력하도록 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

void pushIntoQueue(queue<pair<int, string>>& queue, const pair<int, string>& currentStatus, const pair<int, string>& converted, bool* visited, pair<int, string>* history);

pair<int, string> D(pair<int, string> initialValue);
pair<int, string> S(pair<int, string> initialValue);
pair<int, string> L(pair<int, string> initialValue);
pair<int, string> R(pair<int, string> initialValue);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int numberOfTestCases, initialValue, finalValue;
	string result = "";
	bool visited[10000] = { false, };
	pair<int, string> history[10000];

	queue<pair<int, string>> converted;

	cin >> numberOfTestCases;

	while (numberOfTestCases--) {
		cin >> initialValue >> finalValue;

		converted.push({ initialValue, "" });
		visited[initialValue] = true;

		while (true) {
			pair<int, string> currentStatus = converted.front();
			converted.pop();

			if (currentStatus.first == finalValue) {
				result += currentStatus.second;
				for (int i = finalValue; i != initialValue; i = history[i].first) {
					result += history[i].second;
				}
				reverse(result.begin(), result.end());
				cout << result << "\n";
				break;
			}
			else {
				pushIntoQueue(converted, currentStatus, D(currentStatus), visited, history);
				pushIntoQueue(converted, currentStatus, S(currentStatus), visited, history);
				pushIntoQueue(converted, currentStatus, L(currentStatus), visited, history);
				pushIntoQueue(converted, currentStatus, R(currentStatus), visited, history);
			}
		}

		result = "";

		while (!converted.empty()) {
			converted.pop();
		}

		for (int i = 0; i < 10000; i++) {
			visited[i] = false;
		}
	}

	return 0;
}

void pushIntoQueue(queue<pair<int, string>>& queue, const pair<int, string>& currentStatus, const pair<int, string>& converted, bool* visited, pair<int, string>* history) {
	if (!visited[converted.first]) {
		queue.push(converted);
		visited[converted.first] = true;
		history[converted.first] = currentStatus;
	}
}

pair<int, string> D(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first * 2) % 10000;
	converted.second = "D";

	return converted;
}

pair<int, string> S(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first + 9999) % 10000;
	converted.second = "S";

	return converted;
}

pair<int, string> L(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 1000) * 10 + (initialValue.first / 1000);
	converted.second = "L";

	return converted;
}

pair<int, string> R(pair<int, string> initialValue) {
	pair<int, string> converted;

	converted.first = (initialValue.first % 10) * 1000 + (initialValue.first / 10);
	converted.second = "R";

	return converted;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

처음에 메모리 초과, 틀렸습니다, 시간 초과가 모두 발생했을 때 어이가 없었다. 시간 초과와 틀렸습니다는 많이 봐왔고, 메모리 초과도 종종 본 적은 있지만, 세 개가 한 문제에 모두 나왔던 경우는 처음이었기 때문이다.

그래도 3가지 문제점을 모두 경험했기 때문에, PS에서 자주 당하는 위험 요소를 상기할 수 있게 되었다. 중복 미고려, 변수 미초기화, 비싼 std::string 연산 이 3가지는 다시는 안 까먹도록 머리속에 새겨 두어야 겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/9019

← Previous Post Next Post →