어흥
[백준 14002] 가장 긴 증가하는 부분 수열 4 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/14002
1. 주의할 점
- DP처럼 진행한다
- 가장 긴 증가하는 부분 수열을 어떤 방식으로 담을 건지 생각한다
2. 구현
- 배열을 입력받으면서, Result[]배열도 초기화 작업을 한다
- i: 1~Num-1, j: 0~i-1까지 반복하면서 Arr[i]>Arr[j]를 만족한다면 Result 배열의 인자를 비교하여 이전보다 긴 수열이 가능하면 바꾸고, Arr[i]보다 작은 배열의 idx값을 pre_idx에 저장한다. 만약 길이가 같다면, pre_idx에 저장된 값과 비교하여 바꾸는 것이 더 작으면 바꾼다
- For문이 끝난 후, 가장 긴 수열의 idx값을 저장한다
- While문을 통해 idx의 값이 Result[idx].pre_idx와 같다면, 가장 긴 증가하는 부분 수열의 앞이므로 끝낸다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
int pre_idx, len;
};
int arr[1000], num, idx = 0, max_len = 1;
info result[1001];
vector<int> v;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> num;
for (int i = 0; i < num; i++) {
cin >> arr[i];
result[i].len = 1;
result[i].pre_idx = i;
}
for (int i = 1; i <= num; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
if (result[i].len == result[j].len + 1 && arr[result[i].pre_idx]>arr[j]) {
result[i].pre_idx = j;
}
else if (result[i].len < result[j].len + 1) {
result[i].len = result[j].len + 1;
result[i].pre_idx = j;
}
}
}
}
for (int i = 1; i < num; i++) {
if (result[i].len > max_len) {
max_len = result[i].len;
idx = i;
}
}
while (1) {
v.push_back(arr[idx]);
if (idx == result[idx].pre_idx)
break;
idx = result[idx].pre_idx;
}
cout << v.size() << '\n';
for (int i = v.size() - 1; i >= 0; i--)
cout << v[i] << " ";
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 12738] 가장 긴 증가하는 부분 수열 3 (C++) (0) | 2020.05.17 |
---|---|
[백준 12015] 가장 긴 증가하는 부분 수열 2 (C++) (0) | 2020.05.17 |
[백준 16434] 드래곤 앤 던전 (C++) (0) | 2020.05.17 |
[백준 4650] Jungle Roads (C++) (0) | 2020.05.16 |
[백준 2406] 안정적인 네트워크 (C++) (0) | 2020.05.16 |
Comments