BOJ 2505. 두 번 뒤집기

Leesoft·2022년 10월 28일
0
post-thumbnail

알고리즘 분류에 애드 혹이라는 분류가 있어, 궁금해서 풀어 본 문제였다!

처음에는 애드 혹도 알고리즘의 종류인 줄 알았는데, 내가 아는 의미가 아니라 문제를 해결하기 위해 알려진 알고리즘을 적용하는 것이 아니라 정말 '알아서 생각해서 풀어야 하는 문제'를 일컫는 말이었다.

문제는 1부터 nn까지의 수열을 두 번 뒤집었을 때, 이를 원상복구시키려면 어떻게 뒤집어야 하는지를 묻는다.

알려진 공식이나 방법을 적용할 수 없어서, 우선 여러 개의 예시를 생성하는 방식으로 접근하였다!

그러다 보니, 수열을 뒤집으면 뒤집힌 구간 내부에 있는 숫자들은 인접한 숫자와의 차이가 1 또는 -1이지만 그 경계에 있는 숫자는 인접한 숫자와의 차이가 다르기 때문에, 이 점들을 표시하기로 하였다!

그런데 처음 혹은 맨 마지막 숫자(11 혹은 nn)이 뒤집힌 경우도 생각하기 위해, 수열 맨 앞에 00을 추가하고 맨 뒤에 (n+1)(n+1)을 추가해 주니 간단하게 해결되었다! 이 과정은 답에 영향을 미치지 않지만, 기존의 방법으로 맨 앞 혹은 맨 뒤 숫자에 대해서도 인접한 숫자와 비교하는 방법을 통해 뒤집혔는지의 여부를 알 수 있게 해 준다.

찾아낸 규칙은 다음과 같다!

수열의 각 항 aia_i (2in)(2\le{i}\le{n}) 에 대하여, aiai1a_i - a_{i-1}의 값이 11 또는 1-1이 아닌 ii 값을 전후하여 뒤집기 연산이 발생한다.

뒤집은 횟수가 2번이므로, 이러한 ii 값은 최대 4개가 존재할 수 있고 이를 전후하여 수열을 뒤집는다면 뒤집을 수 있는 경우의 수는 총 8가지가 될 것이다. 따라서 문제를 해결하는 방법은 다음과 같다.

최대 8가지 경우에 따라 각각 수열을 뒤집고 나서, 위의 방법으로 ii의 값을 다시 찾고, 이러한 ii의 값이 0개 또는 2개이면 정답을 찾게 된다. 만약 아니라면, 처음에 뒤집었던 연산을 다시 해서 수열을 뒤집기 전으로 복구한 뒤 다른 2개의 값을 찾아 뒤집기를 시도한다.

테스트

문제를 푸는 방식은 위와 같지만, 이번 문제의 경우 주어지는 수열이 11부터 nn까지의 숫자를 두 번 뒤집는 방식이므로, 내가 임의로 수열을 생성해서 임의의 구간을 2번 뒤집어 테스트 케이스를 생성할 수도 있을 것이다.

그래서 C++의 random 라이브러리를 이용해 난수를 생성한 뒤 테스트 케이스를 만드는 과정까지 시도해 보았다! 규칙을 찾아내기 전에는 이러한 과정을 통해 많은 예시를 찾고, 잘못된 규칙을 찾은 경우에 반례도 표시할 수 있어 코드를 수정하기에 편했다! 마지막으로, TESTSOLVE 상수를 도입하여 모드를 설정함으로써, 테스트와 제출을 같은 코드로 모드만 바꾸어서 할 수 있다는 점이 좋았다. 또, 기존에는 입력을 받고 문제를 풀고 출력을 하는 모든 과정을 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;
}
profile
🧑‍💻 이제 막 시작한 빈 집 블로그...

0개의 댓글