#14002: 가장 긴 증가하는 부분 수열 4

백준 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)

풀이:

• 이 문제 풀이 법은 kwon’s blog의 포스팅을 참고하여 풀었다.
• 이 문제는 #11053: 가장 긴 증가하는 부분 수열 문제와 유사하지만 추가적으로 정답이 되는 수열을 나열 해주어야 된다. 최대 길이를 출력 하는 법은 #11053: 가장 긴 증가하는 부분 수열를 확인하길 바란다.
• 우선, 수열을 나열을 할려면 최대 길이가 바뀔 때 마다 어떤 자리에서 바뀌었는지 기록을 해주어야 나중에 출력을 할 수 있다. 따라서 link라는 추가 배열을 만들어 최대 길이가 바뀔때 마다 인덱스를 기록 해주어 나중에 재귀함수를 통해 그 값을 찾아갈 수 있도록 해준다.
• #11053: 가장 긴 증가하는 부분 수열 문제에서 바뀐점이라면 현재 배열보다 작은 값을 찾는 과정에서 현재 배열보다 작은 경우는 물론이며 최대 길이보다 길이가 커야 되는 조건을 추가하였다. 그 이유는 길이가 최대인 경우에만 link에 기록을 해주어야 다른 값들에 -1이 남아있을 수 있고 오로지 필요한 값만 link에 기록 할 수 있기 때문이다.
• 추가로 달라진 점은 max함수로 d[i]와 ans를 비교하여 최대값을 비교하지 않고 제일 마지막에 저장 된 최대 길이를 기록하기 위하여 if문을 통해 새로운 최대값이 생기면 end 값에 기록하도록 하였다.

코드:

#include <iostream>

using namespace std;

int arr[1000], d[1000]={}, link[1000]={};

//재귀 함수로 link에 기록 된 배열의 위치를 제일 처음부터 출력
void print_ans(int index){
	if(index==-1) return;
	print_ans(link[index]);
	cout<< arr[index] << ' ';
}

int main(){
	int n, end, ans = 0;
	//출력 시 분별을 위하여 모든 값 -1로 초기화
	fill(link, link+1000, -1);
	//입력
	cin >> n;
	for(int i = 0; i < n; i++){
		int max_num = 0; //이전 최대 값과 중첩 안되게 최대 값 0으로 초기화
		cin >> arr[i];
		for(int j = 0; j < i; j++){
			//현재 배열보다 작은 값인 경우와 기록 된 최대 길이보다 큰 경우
			if(arr[i] > arr[j] && max_num < d[j]){
				max_num = d[j]; //최대 길이 재기록 및 
				link[i] = j; //최대 길이의 배열 기록
			}

		}
		d[i] = max_num+1; //자기 자신을 포함하므로 최대 길이 +1
		//전체 입력값 중에 최대 길이를 기록 및 최대 값을 가진 배열 위치 기록
		if(d[i] > ans){ 
			ans = d[i];
			end = i;
		}
	}
	//출력
	cout<<ans<<'\n';
	print_ans(end);
}