[백준] 줄세우기 2631 C++
https://www.acmicpc.net/problem/2631
해설
줄세우기 문제이다.
어떻게 아이들을 옮기면 최소의 횟수로 정렬된 상태를 만들 수 있는지 묻는 문제이다.
직관적으로는 간단한데, 어떠한 기준으로 어떤 수를 옮길지 처음 풀면 알기가 굉장히 힘들다.
본인도 https://www.acmicpc.net/problem/7570 문제 풀다가 안 풀려서 해당 문제 부터 풀었다...ㅎㅎ
해당 문제는 LIS (Longest Increasing Subsequence) 문제이다.
가장 큰 증가하는 부분 수열의 길이만 구해주면 바로 풀린다.
근데 이 문제가 LIS라는것 자체를 생각해내는게 어렵다.
그럼 일단 왜 LIS인지 보자.
3 7 5 2 6 1 4 순으로 있을 때 최소의 이동 횟수를 구하려면 3 5 6 아이들은 이동시키지 말고 7 2 1 4번 아이들만 옮겨주면 최소의 이동 횟수가 나온다.
3 5 6은 이미 정렬되어 있기때문에 또 옮길 필요가 없는 것이다.
즉, LIS의 길이를 구해서 n - LIS의 길이를 해주면 정답이 된다.
본인은 LIS를 DP를 통해서 접근하였다.
문제의 조건 N <= 200이기 때문에 O(N^2)의 풀이와 O(NLogN) 풀이 두가지가 있다.
O(N^2)의 풀이는 이중 루프를 통해 LIS의 길이를 구하는 방식이고 NLogN은 이분 탐색을 통해 가능하다.
아래 코드가 3개가 있다. N^2, lower_bound를 사용한 풀이, 직접 구현한 이분 탐색으로 푼 풀이..
모든 코드를 보고 이해하는 것을 추천한다. 굿.
코드
N^2 풀이
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;
#define endl "\n"
#define ll long long
#define ROW first
#define COL second
#define X first
#define Y second
#define MAX 987654321
int n, arr[204], dp[204];
int main(void)
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
fill(dp + 1, dp + 1 + n, 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
if (arr[j] < arr[i])
dp[i] = max(dp[i], dp[j] + 1);
int _max = *max_element(dp + 1, dp + 1 + n);
cout << n - _max;
}
// <내 생각 & 해설>
// 왜 LIS의 최대값을 n에서 빼나?
// 아이들을 움직이는 최소의 횟수를 구해야한다. 3 7 5 2 6 1 4 순으로 아이들이 있다면 3 5 6 번 아이들은 움직일 필요가 없다. 이미 정렬되어 있기 때문이다.
// 3 5 6 번 아이들을 제외하고 나머지 아이들만 움직여 주면된다. 3 5 6 은 LIS(가장 긴 증가하는 부분 수열)이다.
// 아이들 n명 중에서 LIS의 최대값을 빼주면 이게 아이들을 최소로 움직이는 정답이다.
// n의 최대값이 200이기 때문에 이중 for문으로 LIS 구해주어도 무리가 없다.
NLogN풀이
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;
#define endl "\n"
#define ll long long
#define ROW first
#define COL second
#define X first
#define Y second
#define MAX 987654321
int n, arr[204];
int main(void)
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
vector<int> lis;
for (int i = 1; i <= n; ++i)
{
auto iter = lower_bound(lis.begin(), lis.end(), arr[i]);
if (iter == lis.end())
lis.push_back(arr[i]);
else
*iter = arr[i];
}
cout << n - lis.size();
}
// <내 생각 & 해설>
// https://www.acmicpc.net/source/share/102ac37220c94a87a090fc6817eeb878
// N^2로 풀었던 위의 풀이와 다르게 NLogN으로 푼 풀이이다.
// 정답은 맞지만 실제로 lis배열을 보면 3 5 6 순의 LIS배열은 아니다. 해당 문제는 최소 이동 횟수만 구하면 되기 때문에 문제될 것은 없는듯하다
// (물론 LIS5문제는 이렇게 풀면 틀림 배열하나 더 필요하다)
NLogN 풀이2
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <deque>
#include <vector>
#include <queue>
#include <tuple>
#include <stack>
#include <numeric>
#include <string>
using namespace std;
#define endl "\n"
#define ll long long
#define ROW first
#define COL second
#define X first
#define Y second
#define MAX 987654321
int n, arr[204];
int main(void)
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i];
vector<int> lis;
for (int i = 1; i <= n; ++i)
{
if (lis.size() == 0 || lis.back() < arr[i])
lis.push_back(arr[i]);
else
{
int l = 0, r = lis.size() - 1;
while (l < r)
{
int m = (l + r) / 2;
if (lis[m] < arr[i])
l = m + 1;
else
r = m;
}
lis[l] = arr[i];
}
}
cout << n - lis.size();
}
// <내 생각 & 해설>
// https://www.acmicpc.net/source/share/e7fc760cce354136b9c73eabd9fa5a36
// 위 풀이에 이어서 lower_bound가 아닌 직접 이분 탐색을 만든 풀이다.