[C++] 14003 : 가장 긴 증가하는 부분 수열 5
플래티넘 Ⅴ
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector <int> seq;
int s;
for (int i = 0; i < n; i++) {
scanf("%d", &s);
seq.push_back(s);
}
vector <int> subsq;
subsq.push_back(seq[0]);
vector <int> pos;
pos.resize(n);
pos[0] = 1;
int idx;
for (int i = 1; i < n; i++) {
if (subsq.back() < seq[i]) {
subsq.push_back(seq[i]);
pos[i] = subsq.size();
}
else {
idx = lower_bound(subsq.begin(), subsq.end(), seq[i]) - subsq.begin();
subsq[idx] = seq[i];
pos[i] = idx + 1;
}
}
vector <int> LIS;
int len = subsq.size();
for (int i = n - 1; i >= 0; i--) {
if (pos[i] == len) {
LIS.push_back(seq[i]);
len--;
}
}
printf("%d\n", LIS.size());
while (!LIS.empty()) {
printf("%d ", LIS.back());
LIS.pop_back();
}
}
LIS 알고리즘 (nlogn, LIS 출력)
음.....
일단
입력받은 n개의 배열을 저장하는 벡터가 있어야 하므로
증가하는 부분 수열 3인가에서의 첫 번째 코드 사용 (seq 벡터 있는 코드)
그다음, seq에 있는 아이들이 subsq에 들어갈 때 어디에 들어가는지
(첫 번째? 두 번째? 다섯 번째? -> 인덱스 +1)
기록하는 벡터 pos 만듦
그다음부터는 밑의 예시를 보자
------------------------------------
ex 1)
seq : 10 30 50 20 60 40 80
pos : 1 2 3 2 4 3 5
pos의 맨 뒤에서부터 5, 4, 3, 2, 1의 순서로 읽으면 LIS가 되는 것을 확인할 수 있다
( + 추가 : pos[i]가seq[i]까지의가장 긴 증가하는부분 수열의길이를 의미하게 됨)
그럼 왜 맨 뒤에서부터 5~1의 순서로 읽으면 LIS가 되는가??
이 예제1 같은 경우에는, 10 30 50이 만들어진 순간에서
20 40이 나도 함 부분 수열 만들어볼래 하고 2, 3번째에 들어오지만 (실제로 30 50을 내쫓고 자리를 차지한다)
10 20 40으로 만들어진 부분 수열의 길이는 겨우 3이고
결국 LIS의 길이는 5가 되었으므로
5부터 세면서 내려가면 자동으로 20과 40은 배제된다
그럼 만약 20 , 40으로 만들어진 부분 수열의 길이가 4가 되면?
그럼 된거지 뭐.. 그러면 아마 10 20 40 (어쩌구) 80이 채택될 것이다
왜냐면 뒤에서 부터 읽는데 30 50 은 20 40 보다 앞에 있으니까..
어차피 LIS가 여러개가 존재할 때는 아무거나 하나만 출력하면 된다고 했으므로 문제없다
밑의 접은글은 예시 1에서 subsq가 어떻게 변하는지에 대한 메모이다..
***
ex1) 이어서
10
10 30
10 30 50
10 20 50
10 20 50 60
10 20 40 60
10 20 40 60 80
subsq :
10 20 40 60 80
1 2 3 4 5
seq: 10 30 50 20 60 40 80
pos: 1 2 3 2 4 3 5
답 :
10 30 50 60 80
LIS :
80 60 50 30 10
(답이 거꾸로 들어가게 된다)
***
밑의 예시2는 20, 40으로 이어서 만든 부분 수열이 30, 50~의 부분 수열보다 길어지는 경우이다
보면 이해가 간다..
***
ex2)
seq : 10 30 50 20 60 40 80 50 60 70 80
pos : 1 2 3 2 4 3 5 4 5 6 7
(마찬가지)
10
10 30
10 30 50
10 20 50
10 20 50 60
10 20 40 60
10 20 40 60 80
10 20 40 50 80
10 20 40 50 60
10 20 40 50 60 70
10 20 40 50 60 70 80
subsq :
10 20 40 50 60 70 80
답 :
10 20 40 50 60 70 80
LIS :
80 70 60 50 40 20 10
***
+ 어 이거 근데
pos벡터가 가장 긴 증가하는 부분 수열 어쩌구 1에서의
dp로 푼 풀이와 비슷하다
dp로 풀었을 때 dp[i]는 dp [i]까지의 가장 긴 증가하는 부분 수열의 길이였는데
pos도 그렇게 되네 자연스럽게..!
아하 그렇게 가장 긴 증가하는 부분수열의 길이 4를 풀 수 있는거구나 dp로..
그러면 이 문제를 풀기 위해서는,
-> 일단 subsq가 돌아가는 양상을 볼 때 이 녀석이 새로운 얘는 무조건 업데이트시키고 보니까 예전의 얘들이 어디에 있었는지를 저장해 놓을 필요가 있다는 생각까지는 할 수 있겠다
-> position 벡터를 만듦
-> position 벡터를 보면 seq의 아이들이 어디에 들어갔었는지 정보가 다 나온다
-> position 벡터를 보고, pos[i]가 seq[i]까지의 가장 긴 증가하는 부분 수열의 길이를 의미하게 됨을 깨닫기!!!!
---------------------------------------------------------------
2022.07.14 추가
위의
(-> 일단 subsq가 돌아가는 양상을 볼 때 이 녀석이 새로운 얘는 무조건 업데이트시키고 보니까 예전의 얘들이 어디에 있었는지를 저장해 놓을 필요가 있다는 생각까지는 할 수 있겠다)
를 생각해보면 정보를 다른 방식으로 저장해서 푸는 방법도 있다
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
struct num_info {
int num, idx;
bool operator < (const num_info& ref) const {
return num < ref.num;
}
};
int front_idx[1000000];
int arr[1000000];
int main() {
int N;
scanf("%d", &N);
vector<num_info> subsq;
scanf("%d", &arr[0]);
subsq.push_back({ arr[0], 0});
front_idx[0] = -1;
int low_idx, front_num, front_num_idx;
for (int i = 1; i < N; i++) {
scanf("%d", &arr[i]);
num_info I1 = subsq.back();
front_num = I1.num;
front_num_idx = I1.idx;
num_info I2 = { arr[i], i };
if (front_num < arr[i]) {
subsq.push_back({ arr[i], i });
front_idx[i] = front_num_idx;
}
else {
low_idx = lower_bound(subsq.begin(), subsq.end(), I2) - subsq.begin();
subsq[low_idx] = { arr[i], i };
if (low_idx == 0) front_num_idx = -1;
else front_num_idx = subsq[low_idx - 1].idx;
front_idx[i] = front_num_idx;
}
}
stack<int> s;
s.push(subsq.back().num);
int idx = subsq.back().idx;
while (true) {
if (front_idx[idx] == -1) break;
s.push(arr[front_idx[idx]]);
idx = front_idx[idx];
}
printf("%d\n", s.size());
while (!s.empty()) {
printf("%d ", s.top());
s.pop();
}
}
주의할 점!
lower_bound에 넘겨주는 val 은
비교할 원소들과 같은 type이어야 한다
아니면 연산자 오버로딩 에러 남....