[BOJ][C++] 백준 14002번 가장 긴 증가하는 부분 수열 4
Updated:
14002번 가장 긴 증가하는 부분 수열 4
1. 문제 정보
백준 온라인 저지 [14002번 가장 긴 증가하는 부분 수열 4] 문제의 링크입니다.
문제
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.
예제 입력1
6
10 20 10 30 20 50
예제 출력1
4
10 20 30 50
시간 / 메모리 제한
1초 / 256MB
2. 생각
- 문제 11053번 가장 긴 부분수열과 비슷한 문제였습니다. 문제 11053번과 다른 점은 문제 11053번의 출력인 가장 긴 부분 수열의 길이에다가 그 길이에 해당하는 부분수열도 출력하는 것입니다. 따라서 문제 11053번의 코드를 활용하겠습니다. 시간 복잡도는 그대로 O(n^2)입니다.
- 가장 긴 부분 수열의 길이는 그대로 구하면 되고, 그에 해당하는 부분 수열을 구할 때는 idx배열이 필요합니다. idx[i]는 a[i]의 앞에 올 수의 인덱스로 정의합니다.
- a[i] : 수열의 i 번째 수,
- dp[i] : i 보다 작거나 같은 원소에 대해 가장 긴 증가하는 부분 수열의 길이(원소의 개수),
- idx[i] : a[i]의 앞에 올 수의 인덱스
-
idx[i]를 이렇게 정의한 이유는 a[i]의 앞에 올 수의 인덱스를 통해 수열의 마지막 수부터 맨 앞의 수를 찾아내기 위함입니다. 출력할 때 재귀함수나 스택을 이용하여 순서대로 출력할 수 있습니다.
- idx[i]를 a[i] 앞에 올 수의 인덱스로 정의했기 때문에 a[i]의 앞에는 a[idx[i]]의 수가 옵니다. a[i]가 a[j]의 값보다 크고, dp[i]가 dp[j]보다 작거나 같을 때 dp[i]의 값이 갱신됩니다.
이때, idx[i]의 값도 두 수중 작은 수인 dp[j]의 인덱스 j의 값을 넣습니다.
a 배열
1 2 3 4 5 6 10 20 10 30 20 50 dp 배열
i=1 2 3 4 5 6 개수 10 1개 10 20 2개 10 1개 10 20 30 3개 10 20 2개 10 20 30 50 4개 -
그리고 부분 수열의 가장 긴 값은 max 입니다. idx 배열을 통해 거꾸로 찾아가기 위해서 max_idx 변수를 통해 가장 긴 값의 인덱스도 저장합니다.
- 저는 STL 자료구조 vector와
헤더의 reverse 함수를 통해 스택을 구현했습니다.
i 1 2 3 4 5 6 A 10 20 10 30 20 50 idx 0 1 0 2 1 4 순서 네번쨰 세번째 두번째 첫번쨰
- 순서 (인덱스) : 6 -> 4 -> 2 -> 1
( idx[6] -> idx[4] -> idx[2] -> idx[1])- 순서 (값) : 50 -> 30 -> 20 -> 10
( A[idx[6]] -> A[idx[4]] -> A[idx[2]] -> A[idx[1]])출력은 거꾸로.
3. 소스코드 (C++)
