https://www.acmicpc.net/problem/14002
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.
N = 1000 인 LIS 문제로 O(N^2)의 시간이 걸리는 DP를 활용한 LIS 알고리즘을 사용하여 풀 수 있는 문제이다. LIS의 배열을 구할 때 이전 원소가 몇 번째 원소인지 저장해놨다가 역추적하여 문제를 풀 수 있다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N;
int arr[1000001], dp[1000001], memo[1000001],lis[1000001];
int ans=0,ans_idx=0,lis_cnt=0;
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) cin >> arr[i];
memset(dp, 0, sizeof(dp));
memset(memo, -1, sizeof(memo));
for (int i = 0; i < N; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
memo[i] = j;
}
}
if (ans < dp[i]) {
ans = dp[i];
ans_idx = i;
}
}
while (1) {
lis[lis_cnt++] = arr[ans_idx];
if (memo[ans_idx] == -1) break;
ans_idx = memo[ans_idx];
}
cout << ans << "\n";
for (int i = lis_cnt-1 ; i >= 0; i--) {
cout << lis[i] << " ";
}
}
사실 14003번 문제를 풀다가 시간초과가 나서 보니 N이 백만이었다. 그래서 알고리즘을 찾아보는 중 앞 번호 문제가 N 이 천으로 시간 초과가 안 날 것 같아 시간 초과 난 코드 그대로 제출하였더니 통과하였다. 저번에 알고리즘 정리를 할 때 LIS는 DP로 정리를 해놨는데 그때는 왜 이진 탐색을 활용한 O(NlogN)의 풀이를 보지 못한 지 의문이다..
'코딩 > 백준' 카테고리의 다른 글
[백준]10282번 해킹 - C/C++ (0) | 2022.03.03 |
---|---|
[백준]14003번 가장 긴 증가하는 부분 수열 5 - C/C++ (0) | 2022.03.02 |
[백준]1202번 보석도둑 - C/C++ (0) | 2022.03.01 |
[백준]1238번 파티 - C/C++ (2) | 2022.02.28 |
[백준]4195번 친구 네트워크 - C/C++ - STL 사용 (0) | 2022.02.25 |