문제링크
https://www.acmicpc.net/problem/7570
문제
키 포인트
생각1.
무작위 순서로 배열된 숫자들을 정렬하기 위한 최소 횟수가 얼마일까?
생각2.
가장 긴 증가하는 부분수열 문제를 떠올리면 정렬하기 위한 최소 이동 횟수를 알아낼 수 있다. 증가하는 부분 수열은 이미 정렬되어 있다고 판단하고 나머지 숫자만 잘 배열하면 되기 때문이다.
즉, 1 5 2 4 3 7 6 8 이라는 숫자가 있다면 가장 긴 증가하는 부분수열 중 하나는 1 2 4 6 8 이므로 나머지 숫자인 5 3 7을 올바른 자리에 끼워넣으면 되므로 3번만 움직이면 올바르게 정렬을 할 수 있다.
그런데 이 문제는 숫자를 골라서 맨 뒤나 맨앞으로 밖에 보내지 못한다. 즉 일반적인 증가하는 부분수열 문제와 달리 움직임에 제한이 있다.
생각3.
그럼 어떨때 최소의 정렬 횟수를 찾아낼 수 있을까?
맨 앞이나 맨 뒤로밖에 못보낸다는 것은 가운데에는 끼워넣을 수 없다는것이다. 즉, 증가하는 부분수열이면서 연속된 숫자일때 이미 정렬이 되어있는 상태라고 판단 할 수 있다.
1 5 2 4 3 7 6 8 에서는 1 2 3이 가장긴 연속으로 증가하는 부분수열이다. 이후에는 나머지 숫자를 맨앞이나 뒤로 옮기며 정렬을 한다
1 5 2 4 3 7 6 8
1 5 2 3 7 6 8 4
1 2 3 7 6 8 4 5
1 2 3 7 8 4 5 6
1 2 3 8 4 5 6 7
1 2 3 4 5 6 7 8 (완성)
1 2 3이 원래 정렬되어 있었으므로 총 8-3 = 5번의 이동을 통해 정렬이 가능하다.
생각4.
어떤식으로 찾을 수 있을까?
배열의 인덱스에 해당 인덱스에 해당하는 숫자가 어디에 위치하는지를 저장하면 된다. 그러니까 arr[i]에는 i라는 숫자가 몇번째 위치에 저장하면 된다.
그렇게 하면 i+1이 i보다 뒤에있는지 판단 할 수 있고, 연속적으로 증가하는 수열인지 판단이 가능하다.
시행착오
https://mygumi.tistory.com/276
3번까지는 생각이 닿았는데 풀이에서 막혀 해당 블로그에서 힌트를 얻어 풀었다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int arr[1000001];
cin >> n;
for (int i = 0; i < n; i++) {
int t; cin >> t;
arr[t] = i;
}
int maxn = 0;
int temp_max = 1;
for (int i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1]) maxn = max(maxn, ++temp_max);
else temp_max = 1;
}
cout << n - maxn;
}후기
구현이 어려운 문제는 아니었는데 아이디어가 떠올리기 힘들었다.
