| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 641 | 304 | 238 | 55.738% |
문제
동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 오른쪽으로 순서대로 1∼N번의 책들로 재배열하길 원한다.
동혁이가 책들을 배열하는 방법은 어떠한 책 하나를 꺼내서 다른 위치에 꽂는 방법이다.
1 5 2 3 4위와 같이 책이 배열되어 있을 때 5번 책을 꺼내 가장 뒤쪽에 꼽으면
1 2 3 4 5로 배열되고, 1∼5번까지 순서대로 책이 꽂히면서 정리는 끝나게 된다.
문제는 현재 책들의 배열순서가 주어지면 최소 횟수로 책들을 옮겨 책 정리를 끝내는 것이다
입력
첫째 줄에 책의 개수 N(1 ≤ N ≤ 200,000)이 주어진다. 두 번째 줄에는 현재 책들이 배열된 순서가 공백으로 구분되어 주어진다.
출력
동혁이가 책들을 옮겨야 하는 최소 횟수를 출력한다.
접근
생각해보면, 책이 순서대로 꽂혀 있는 가장 긴 길이를 구해서 전체에서 빼주면 된다.
LIS라고 불리는 가장 긴 증가하는 부분수열 문제와 동일하다.
다만, N이 20만이기 때문에 O(NlogN)의 알고리즘을 사용해야 한다.
풀이
vector를 만들어 이분탐색으로 맞는 위치를 찾아주는 알고리즘을 사용한다.
v.back()보다 지금 값이 큰 경우는 최대 길이가 증가하는 경우이다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, num, ans = 0;
vector<int> v;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(N);
v.push_back(0);
FUP(i, 1, N)
{
CIN(num);
if (num > v.back())
{
v.push_back(num);
ans++;
}
else
{
auto iter = lower_bound(ALL(v), num);
*iter = num;
}
}
COUT(N - ans);
return 0;
}
Beginner