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

2505번: 두 번 뒤집기

 

문제

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

2505번: 두 번 뒤집기

 

 

풀이

먼저 왼쪽에서 오른쪽으로 진행하며 i번째 칸의 수가 i가 아닌 경우 i의 위치를 찾아 두 위치를 정답 배열에 추가하고 두 위치 사이의 모든 값을 reverse 한다. 그러면 i번째 칸의 수는 i가 되었으므로 다음 수로 넘어가 위 과정을 반복한다.

 

만약 정답 배열의 크기가 2보다 큰 경우, 답이 될 수 없으므로 위에서 했던 과정을 오른쪽에서 왼쪽으로 진행한다. 이유는 "단 두 번만 뒤집기 때문"이다. 정확히는 두 번째 뒤집은 위치는 처음 뒤집은 위치를 기준으로 왼쪽이 겹치거나 오른쪽이 겹치거나 둘 중 하나이기 때문이다.

 

정답 배열의 크기가 반드시 2 이하일 수밖에 없게 되고, 크기가 2인 경우에는 배열의 값을 모두 출력하면 된다. 크기가 1인 경우는 위치 i와 j는 i ≤ j 를 만족하기 때문에 같을 수 있으므로 1 1을 출력한다. (꼭 1이 아니어도 같은 숫자면 된다.) 마찬가지로 크기가 0인 경우에는 처음부터 정렬되어 있는 배열이었으므로 1 1을 두 번 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> input(n), v;
  vector<pair<int, int>> ans;
  for (int i = 0; i < n; i++)
    cin >> input[i];
  v = input;
  for (int i = 0; i < n; i++) {
    if (v[i] == i + 1)
      continue;
    for (int j = i + 1; j < n; j++)
      if (v[j] == i + 1) {
        ans.push_back({i + 1, j + 1});
        reverse(v.begin() + i, v.begin() + j + 1);
        break;
      }
  }
  if (ans.size() > 2) {
    ans.clear();
    v = input;
    for (int j = n - 1; j >= 0; j--) {
      if (v[j] == j + 1)
        continue;
      for (int i = j - 1; i >= 0; i--)
        if (v[i] == j + 1) {
          ans.push_back({i + 1, j + 1});
          reverse(v.begin() + i, v.begin() + j + 1);
          break;
        }
    }
  }
  if (ans.size() == 2)
    for (auto [a, b] : ans)
      cout << a << ' ' << b << '\n';
  else if (ans.size() == 1)
    cout << ans[0].first << ' ' << ans[0].second << "\n1 1";
  else
    cout << "1 1\n1 1";
  return 0;
}