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

백준 11053번: 가장 긴 증가하는 부분 수열

문제:

수열 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)

풀이:

• 이 문제 풀이 법은 Seungkwan’s Lab님의 포스팅을 참고하여 풀었다.
• 이 문제는 바텀업 방식을 이용하여 풀었고 이중 for문을 이용하여 첫번째 for문에는 모든 자리를 확인 해주며 두번째 for문에는 현재 확인 중인 배열의 이전 값들을 전부 현재 배열 값과 비교하여 작은 값들 중에 길이가 제일 긴 값에 1을 더한 값을 저장한다. 그렇게 저장 한 뒤 길이 중에 최대 값을 기록하여 출력 해주면 된다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, ans = 0, arr[1001], d[1001]={};
	//입력
	cin >> n;
	for(int i = 0; i<n; i++){
		int max_num = 0; //이전 최대 값과 중첩 안되게 최대 값 0으로 초기화
		cin >> arr[i];
		for(int j = 0; j<i; j++){
			//현재 배열보다 작은 값인 경우 그 중 d[]에 저장 된 최대 길이의 값을 기록
			if(arr[j] > arr[i]) max_num = max(max_num, d[j]);
		}
		d[i] = max_num+1; //자기 자신을 포함하므로 최대 길이 +1
		ans = max(ans, d[i]); //전체 입력값 중에 최대 길이를 기록
	}
	//출력
	cout << ans;
}