알고리즘 분류에 애드 혹이라는 분류가 있어, 궁금해서 풀어 본 문제였다!
처음에는 애드 혹도 알고리즘의 종류인 줄 알았는데, 내가 아는 의미가 아니라 문제를 해결하기 위해 알려진 알고리즘을 적용하는 것이 아니라 정말 '알아서 생각해서 풀어야 하는 문제'를 일컫는 말이었다.
문제는 1부터 까지의 수열을 두 번 뒤집었을 때, 이를 원상복구시키려면 어떻게 뒤집어야 하는지를 묻는다.
알려진 공식이나 방법을 적용할 수 없어서, 우선 여러 개의 예시를 생성하는 방식으로 접근하였다!
그러다 보니, 수열을 뒤집으면 뒤집힌 구간 내부에 있는 숫자들은 인접한 숫자와의 차이가 1 또는 -1이지만 그 경계에 있는 숫자는 인접한 숫자와의 차이가 다르기 때문에, 이 점들을 표시하기로 하였다!
그런데 처음 혹은 맨 마지막 숫자( 혹은 )이 뒤집힌 경우도 생각하기 위해, 수열 맨 앞에 을 추가하고 맨 뒤에 을 추가해 주니 간단하게 해결되었다! 이 과정은 답에 영향을 미치지 않지만, 기존의 방법으로 맨 앞 혹은 맨 뒤 숫자에 대해서도 인접한 숫자와 비교하는 방법을 통해 뒤집혔는지의 여부를 알 수 있게 해 준다.
찾아낸 규칙은 다음과 같다!
수열의 각 항 에 대하여, 의 값이 또는 이 아닌 값을 전후하여 뒤집기 연산이 발생한다.
뒤집은 횟수가 2번이므로, 이러한 값은 최대 4개가 존재할 수 있고 이를 전후하여 수열을 뒤집는다면 뒤집을 수 있는 경우의 수는 총 8가지가 될 것이다. 따라서 문제를 해결하는 방법은 다음과 같다.
최대 8가지 경우에 따라 각각 수열을 뒤집고 나서, 위의 방법으로 의 값을 다시 찾고, 이러한 의 값이 0개 또는 2개이면 정답을 찾게 된다. 만약 아니라면, 처음에 뒤집었던 연산을 다시 해서 수열을 뒤집기 전으로 복구한 뒤 다른 2개의 값을 찾아 뒤집기를 시도한다.
문제를 푸는 방식은 위와 같지만, 이번 문제의 경우 주어지는 수열이 부터 까지의 숫자를 두 번 뒤집는 방식이므로, 내가 임의로 수열을 생성해서 임의의 구간을 2번 뒤집어 테스트 케이스를 생성할 수도 있을 것이다.
그래서 C++의 random
라이브러리를 이용해 난수를 생성한 뒤 테스트 케이스를 만드는 과정까지 시도해 보았다! 규칙을 찾아내기 전에는 이러한 과정을 통해 많은 예시를 찾고, 잘못된 규칙을 찾은 경우에 반례도 표시할 수 있어 코드를 수정하기에 편했다! 마지막으로, TEST
와 SOLVE
상수를 도입하여 모드를 설정함으로써, 테스트와 제출을 같은 코드로 모드만 바꾸어서 할 수 있다는 점이 좋았다. 또, 기존에는 입력을 받고 문제를 풀고 출력을 하는 모든 과정을 main()
에서 진행했는데, 별도로 solve()
함수를 만들어 진행하는 것이 더 낫다는 생각이 들었다!
int main() {
int MODE = SOLVE;
if (MODE == TEST) {
test();
} else if (MODE == SOLVE) {
// input, solve, output...
}
return 0;
}
아직 프로그래밍 대회에 나가는 건 생각해보지 않았지만, 어떤 대회에서는 코드를 제출했을 때 테스트를 통과하지 못하면 감점이 되기도 한다고 하니 이렇게 미리 테스트 케이스를 만들고 반례를 찾으면 좋을 것 같다!
// BOJ 2505. 두 번 뒤집기
#define TEST 1
#define SOLVE 2
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <random>
void flip(std::vector<int> &v, int i, int j) {
std::vector<int> tmp;
for (int k=0; k<v.size(); k++) {
if (i <= k && k <= j) tmp.push_back(v[i + j - k]);
else tmp.push_back(v[k]);
}
v.clear();
v = tmp;
}
int solve(std::vector<int> &v) {
// Find indices i, where |v[i] - v[i - 1]| != 1. Let the indices be unique_indices.
// Since there are two flips, there will be at most 4 unique_indices.
// However, a flip can happen either before or after unique_indices,
// so let's add the adjacent indice of unique_indices for a candidate.
// Then there will be at most 8 candidates.
std::vector<int> unique_indices_1;
for (int i=1; i<v.size(); i++)
if (v[i] - v[i - 1] != -1 && v[i] - v[i - 1] != 1) {
unique_indices_1.push_back(i);
if (i + 1 < v.size()) unique_indices_1.push_back(i + 1);
}
std::sort(unique_indices_1.begin(), unique_indices_1.end());
if (unique_indices_1.empty()) {
// Trivial base case.
std::cout << "1 1\n1 1" << std::endl;
} else if (unique_indices_1.size() == 2) {
// If the size of 'unique_indices_1' is 2, then answer is [unique_indices[0], unique_indices[1] - 1].
flip(v, unique_indices_1[0], unique_indices_1[1] - 1);
std::cout << unique_indices_1[0] << " " << unique_indices_1[1] - 1 << std::endl;
std::cout << "1 1" << std::endl;
return 0;
} else {
// Given unique indices, choose 2 and flip.
// If there are 2 unique indices after flip, then flip with these 2 unique indices to get answer.
// If not, restore the vector and try with other pair.
std::vector<int> filter (unique_indices_1.size() - 2, -1);
filter.push_back(0);
filter.push_back(0);
do {
// Choose 2 indices and flip.
int i1 {-1}, j1 {-1};
for (int k=0; k<filter.size(); k++) {
if (filter[k] == 0 && i1 == -1) i1 = unique_indices_1[k];
if (filter[k] == 0 && i1 != -1) j1 = unique_indices_1[k];
}
flip(v, i1, j1 - 1);
// Count unique indices.
std::vector<int> unique_indices_2;
for (int i=1; i<v.size(); i++)
if (v[i] - v[i - 1] != -1 && v[i] - v[i - 1] != 1) unique_indices_2.push_back(i);
std::sort(unique_indices_2.begin(), unique_indices_2.end());
// If there are two unique indices, then flip with them to get answer.
// Otherwise restore and try again.
if (unique_indices_2.size() == 2) {
flip(v, unique_indices_2[0], unique_indices_2[1] - 1);
std::cout << i1 << " " << j1 - 1 << std::endl;
std::cout << unique_indices_2[0] << " " << unique_indices_2[1] - 1 << std::endl;
return 0;
} else {
flip(v, i1, j1 - 1);
}
} while (std::next_permutation(filter.begin(), filter.end()));
}
return -1;
}
void test() {
std::cout << "TEST STARTS..." << std::endl;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dis(5, 30);
int test_counter {0};
while (1) {
int n = dis(gen);
std::uniform_int_distribution<int> r(1, n - 1);
std::vector<int> vec {0};
for (int i=1; i<=n; i++) vec.push_back(i);
vec.push_back(n + 1);
int i1, j1, i2, j2;
{
int i = r(gen); int j = r(gen);
i1 = std::min(i, j); j1 = std::max(i, j);
i = r(gen); j = r(gen);
i2 = std::min(i, j); j2 = std::max(i, j);
}
flip(vec, i1, j1); flip(vec, i2, j2);
std::cout << "\nTEST " << ++test_counter << ".\nvec: ";
for (int i=1; i<vec.size() - 1; i++) std::cout << vec[i] << " ";
std::cout << std::endl;
if (solve(vec) != 0) {
std::cout << "ANSWER : [" << i2 << ", " << j2 << "] -> [" << i1 << ", " << j1 << "]" << std::endl;
std::cout << "TEST FAILED" << std::endl;
break;
} else {
std::cout << "TEST PASSED" << std::endl;
}
}
}
int main() {
int MODE = SOLVE;
if (MODE == TEST) {
test();
} else if (MODE == SOLVE) {
int n;
// Adding v[0] = 0 and v[n + 1] = n + 1 does not affect the answer.
std::vector<int> vec {0};
// Input
std::cin >> n;
for (int i=0; i<n; i++) {
int x;
std::cin >> x;
vec.push_back(x);
}
vec.push_back(n + 1);
solve(vec);
}
return 0;
}