[BOJ] 2505 두 번 뒤집기

링크

BOJ 2505

난이도

플레티넘 5

문제 설명

숫자판의 크기를 나타내는 정수 N (5<= N <= 10000) 과 두 개의 구간이 뒤집혀진 놀이판의 상태가 주어짐.

문제 접근

10
6 7 8 2 1 5 4 3 9 10

주어진 예제를 보면, arr[i] 에 i가 아닌 값이 저장되어 있는 경우가 있는데, 1의 경우 arr[1]이 아닌 arr[5]에 저장되어 있다!

1을 arr[1]의 자리로 보내기 위해서 swap(1, 5)가 포함되어야 할 것 같다.

방법 1.

양쪽에서 arr[idx] == idx를 만족하지 않는 첫번째 수 left_val, right_val을 찾고 정렬해보자.

1. left_val, left_idx 구하기 (right_val 생략)

vector<int> point(vector<int> vec)
{
    vector<int> result;
    int left_val = 1;
    int left_idx = 1;
    // left_val 의 위치
    
    while (left_val == vec[left_val] && left_val < N + 1)
        left_val = ++left_idx;
    while (vec[left_idx] != left_val)
        left_idx++;
    result.push_back(left_val);
    result.push_back(left_idx);
    return result;
}

위와 같은 방법으로 right_val, right_idx도 구해준다.

2. swap(left_val, left_idx)? swap(right_val, right_idx)?

판을 뒤집을 때, 왼쪽부터 뒤집을지 오른쪽부터 뒤집을지 알 수 없다.
따라서 두 경우 전부 따져주도록 하자.

vector<int> change(int start, int end, vector<int> arr)
{
    vector<int> result = arr;
    while (start < end)
    {
        int temp = result[start];
        result[start] = result[end];
        result[end] = temp;
        start++;
        end--;
    }
    return result;
}

change함수는 start부터 end까지 바꾸어준 결과를 vector 형식으로 return 한다.

3. 옳은 경우 판별

   이미 한번 swap한 판에서 다시 left_val, right_val을 찾아보자!

   이전에 한번 뒤집는게 맞는 선택이었다면

   left_val == right_idx && left_idx == right_val

   을 만족하는 것은 자명하다!

vector<int> v1 = change(result[0], result[1], v); // 왼쪽에서 뒤집은 결과
    vector<int> result1 = point(v1); {left_val, left_idx, right_idx, right_val}
    if (result1[0] == result1[2] && result1[1] == result1[3])
    {
        cout << result[0] << ' ' << result[1] << '\n'
             << result1[0] << ' ' << result1[1] << '\n';
        return;
    }

4. 반례 찾기
   left_val, right_val을 구하는 과정에서 판이 이미 정렬되어 있는 경우

   1 2 3 4 5 6 7 8 9 10

   left_val은 계속 커지고, right_val은 계속 감소한다.
   반례 처리를 해주자!
   

if (!right_val) // left_val = left_idx = right_val = right_idx = 1
  {
      result.push_back(1);
      result.push_back(1);
      result.push_back(1);
      result.push_back(1);
      return result;
  }

소스코드

#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> v;
void two();
vector<int> point(vector<int>);
vector<int> change(int, int, vector<int>);
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    two();
}
void two()
{
    cin >> N;
    v.push_back(-1);
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }
    v.push_back(-1);
    vector<int> result = point(v);
    vector<int> v1 = change(result[0], result[1], v);
    vector<int> result1 = point(v1);
    if (result1[0] == result1[2] && result1[1] == result1[3])
    {
        cout << result[0] << ' ' << result[1] << '\n'
             << result1[0] << ' ' << result1[1] << '\n';
        return;
    }
    vector<int> v2 = change(result[2], result[3], v);
    vector<int> result2 = point(v2);
    if (result2[0] == result2[2] && result2[1] == result2[3])
        cout << result[2] << ' ' << result[3] << '\n'
             << result2[0] << ' ' << result2[1] << '\n';
}
vector<int> point(vector<int> vec)
{
    vector<int> result;
    int left_val = 1;
    int left_idx = 1;
    int right_val = N;
    int right_idx = N;
    while (right_val == vec[right_val] && right_val > 0)
        right_val = --right_idx;
    if (!right_val)
    {
        result.push_back(1);
        result.push_back(1);
        result.push_back(1);
        result.push_back(1);
        return result;
    }
    while (left_val == vec[left_val] && left_val < N + 1)
        left_val = ++left_idx;
    while (vec[left_idx] != left_val)
        left_idx++;
    while (vec[right_idx] != right_val)
        right_idx--;
    result.push_back(left_val);
    result.push_back(left_idx);
    result.push_back(right_idx);
    result.push_back(right_val);
    return result;
}
vector<int> change(int start, int end, vector<int> arr)
{
    vector<int> result = arr;
    while (start < end)
    {
        int temp = result[start];
        result[start] = result[end];
        result[end] = temp;
        start++;
        end--;
    }
    return result;
}