�ݺ�ߣ

STUDENTSKO
BOJ 10547
2020-12-04
김봄

SAMPLE INPUT/OUTPUT
9 12 5 13 5 9 12 13
16 2 1 7 5 10 2 1 7 5 16 10
7 9 8 3 6 5 7 9 8
3 6 5
4 1
9 12 5 13
6 2
16 2 1 7 5 10
6 3
7 9 8 3 6 5
1
1
3

SOLUTION
정렬을 통해 각 원소가 몇 번째 블록으로 가야 하는지 계산한다.
(블록 내에서 순서는 바뀌어도 블록이 바뀌진 않는다.)
이미 정렬이 완료된 원소는 움직일 필요가 없다.
따라서 이미 정렬이 완료된 원소의 개수를 세면 정답을 찾을 수 있다.
가야 할 블록의 최장 증가 부분 수열(LIS)의 길이가 이미 정렬이 완료된 원소의 개수이다.

CODE
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, K;
vector<int> v;
int main() {
cin >> N >> K;
v.assign(N, 0);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
vector<pair<int, int>> sorted;
vector<pair<int, int>> unsorted;
for (int i = 0; i < N; i++) {
sorted.push_back(make_pair(v[i], i));
unsorted.push_back(make_pair(v[i], i));
}
sort(sorted.begin(), sorted.end());
for (int i = 0; i < sorted.size(); i++) {
unsorted[sorted[i].second].second = i / K + 1;
}
int max_idx = 0; //LIS(Longest Increasing Subsequence)
vector<int> dp(N);
for (int i = 0; i < N; i++) {
int idx = upper_bound(dp.begin(), dp.begin() + max_idx, unsorted[i].second) - dp.begin();
if(idx == max_idx)max_idx++;
dp[idx] = unsorted[i].second;
}
cout << N - max_idx << endl;
return 0;
}

EXPLANATION
최장 증가 부분 수열, Longest Increasing Subsequence, LIS
[3, 5, 1, 9, 2, 1, 4, 8]과 같은 수열에서 임의의 수를 제거해 정렬된 상태인 부분 수열을 구하는데 길이가 최대가 되는 부
분 수열을 찾는 문제가 최장 증가 부분 수열 문제이다.
알고리즘을 정리하자면 아래와 같다.
현재 원소를 DP 배열의 정렬이 되도록 덮어씌운다. (삽입 X)
예를 들어 DP 배열에 [1, 4, 8]이 있다면 3을 어디에 덮어씌워야 정렬이 유지가 되는가이다. 4를 3으로 대체한다면 [1, 3,
8]이 되어 정렬을 유지할 수 있다.
DP 배열의 길이가 최장 증가 부분 수열의 길이이다.

EXPLANATION
idx
max
dp배열의 크기는 1이였고 3은 들어갈 공간이 하나 밖에 없으니 그대로 삽입한다.

EXPLANATION
idx
max
dp 배열은 [3][ ] 이였고 5는 마지막 원소가 되어야 한다.

EXPLANATION
idx
max
dp 배열은 [3][5][ ] 이였고, 1은 맨 처음 원소가 되어야 한다.
맨 뒤에 들어가는 경우가 아니면 dp 배열의 길이는 늘어나지 않는다.

EXPLANATION
idx
max
dp 배열은 [1][5][ ] 이였고, 9는 마지막 원소가 되어야 한다.

EXPLANATION
idx
max
dp 배열은 [1][5][9][ ] 이였고 2는 5의 자리를 대체하면 된다.

EXPLANATION
idx
max
dp 배열은 [1][2][9][ ] 이였고 1은 맨 앞으로 가면 된다.

EXPLANATION
idx
max
dp 배열은 [1][2][9][ ] 이였고 4는 9의 자리를 대체한다.

EXPLANATION
idx
max
dp 배열은 [1][2][4][ ] 이였고 8은 마지막 자리로 가면 된다.
최장 증가 부분 수열은 길이가 4이다.

�ݺ�ߣ

BOJ10547_STUDENTSKO_LIS(Longest Increasing Subsequence) Algorithm

Recommended

More Related Content

Similar to BOJ10547_STUDENTSKO_LIS(Longest Increasing Subsequence) Algorithm (20)

More from Bomm Kim (6)

BOJ10547_STUDENTSKO_LIS(Longest Increasing Subsequence) Algorithm