[백준 C++ ] 2505 두 번 뒤집기

문제

1부터 N까지의 숫자가 각 칸에 차례대로 들어있는 놀이판이 있다. 예를 들어 10 칸을 가진 놀이판의 초기 상태는 다음과 같다.

구간[i,j]는 놀이판의 왼쪽 i번째 칸부터 j번째칸 사이에 있는 모든 숫자를 말한다. 단 구간[i,j]에서 항상 i ≤ j라고 가정한다. 우리는 이 놀이판의 한 구간을 잡아서 그 구간을 완전히 뒤집을 수 있다. 만일 초기상태에서 구간[3,8]을 뒤집으면 놀이판은 다음과 같이 변한다.

이어 이 상태에서 구간[1,5]를 다시 뒤집으면 놀이판은 다음과 같이 바뀐다.

여러분은 두 번 뒤집힌 놀이판의 상태를 입력으로 받아서 이를 다시 초기 상태로 돌리기 위해서 어떤 두 구간을 차례대로 뒤집어야 하는지를 계산해야 한다. 즉 여러분이 찾아낸 두 개의 구간대로 입력 놀이판을 차례대로 뒤집으면, 놀이판은 초기상태인 1, 2, 3, ...., N 으로 되돌아가야 한다.

단 어떤 경우에는 초기상태로 되돌릴 수 있는 두 구간이 여러 개 있을 수도 있는데, 그러한 경우에는 그 중 하나만 출력해도 된다. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다.

입력

첫줄에는 숫자판의 크기를 나타내는 정수 N (5 ≤ N ≤ 10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다.

출력

첫 두 줄에는 뒤집어야 할 각 구간을 차례대로 출력해야 한다. 각 줄에는 구간[i,j]를 나타내는 i와 j를 빈 칸을 사이에 두고 출력해야 한다. 입력에 대한 답은 항상 존재한다.

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

풀이

주어지는 수열의 일부분을 뒤집고, 다시 그 수열의 일부분을 뒤집어서
오름차순 정렬이 되면 그때 뒤집은 구간을 차례대로 출력하는 문제이다.
결과적으로 1이 맨앞, N이 맨뒤에 위치해야하는데, 여기서 힌트를 얻자면, 숫자1을 포함한 수열의 일부분이 두번 뒤집혔을때 맨 앞으로 와야한다.
그러면 숫자2를 포함한 수열의 일부분이 두번 뒤집혀서 맨 앞으로 와야한다.
'''
이에 포함되지않는경우는 바로
숫자n이 해당n번째에 위치할때이다. 이때는 이미 정렬됬으므로 패쓰하고 다음 숫자를탐색한다
따라서 앞에서부터 탐색하다가, n번째에 숫자n이 없는 수가 발견되면
해당 n을 기록하고,
이후 탐색에서 찾고자하는 숫자n을 발견하면
좀전에 n을 찾은 위치~발견한위치의 일부분을 뒤집으면 되는것.
이것을 두번 반복하면 오름차순 수열을 얻을수 있다.

하지만,
이러한 수열에서는 2번이아닌 총 7번을 뒤집어야 오름차순 정렬이된다.

하지만 탐색을 뒤에서 앞으로 역으로 진행한다면,
이런 경우에는 2번만에 오름차순정렬이 가능하다.
즉, 처음에는 앞에서부터 탐색하여 2번만에 정렬되는지확인,
그이상 횟수면 반복을 멈추고
다시 뒤에서 부터 앞으로 탐색을 진행하면된다.

이때 0번뒤집거나 1번뒤집어서 오름차순되는 경우가 있으므로,
해당경우일땐 각각 원하는 인덱스i(0 <= i < N)를 구간으로 (i, i)를 뒤집은것으로 출력하면된다.
필자는 1, 1을 뒤집은것으로 출력하였다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define len(x) x.length()
#define sz(x) ((int)x.size())
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) (x).begin(),(x).end() //sort등에서 컨테이너 전체를 처리해야할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define MAX 10001
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill;
//_UG std::max; //_UG std::min; //_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
template <class T> inline T sq(T num) { rt num* num; }//제곱함수
template <class T> inline T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
template <class T> inline T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
template <class T> inline void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
template <class T> inline void msv(T& a) { a.cls(); }//vector clear
template <class T> inline void msdq(T& a) { a.cls(); }//deque clear
template <class T> inline void msm(T& a) { a.cls(); }//map clear
template <class T> inline void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
template <class T> inline void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

int N;
vi seq1, seq2;

void init();
void func();

void init() {
    sc("%d", &N);
    rep(i, N) {
        int element;
        sc("%d", &element);
        seq1.pb(element);
        seq2.pb(element);
    }
}

void func() {
    vi start, end;
    int cnt = 0;
    //앞에서부터
    while (1) {
        int idx = -2;
        rep(i, N) {
            int cur = seq1[i];
            if (idx == -2 && cur != i + 1) {
                idx = i;
                start.pb(i + 1);
            }
            if (cur == idx + 1) {
                reverse(range(seq1, idx ,i + 1));
                end.pb(i + 1);
            }
        }
        if (idx == -2) br;
        if (cnt >= 3) br;
        cnt++;
    }
    
    if (cnt == 3) {
        start.cls();
        end.cls();
        cnt = 0;
        //뒤에서부터 다시탐색
        while (1) {
            int idx = -2;
            _rrep(i, N-1, 0) {
                int cur = seq2[i];
                if (idx == -2 && cur != i + 1) {
                    idx = i;
                    end.pb(i + 1);
                }
                if (cur == idx + 1) {
                    reverse(range(seq2, i, idx + 1));
                    start.pb(i + 1);
                }
            }
            if (idx == -2) br;
            if (cnt >= 3) br;
            cnt++;
        }
    }
    if(cnt == 0)
        pr("1 1\n1 1");
    else if (cnt == 1) 
        pr("%d %d\n1 1", start[0], end[0]);
    else if (cnt == 2)
        pr("%d %d\n%d %d", start[0], end[0], start[1], end[1]);

}

int main(void) {
    init();
    func();

    rt 0;
}