#11722: 가장 긴 감소하는 부분 수열

백준 11722번: 가장 긴 감소하는 부분 수열

문제:

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력:

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

풀이:

• 이 문제는 #11053: 가장 긴 증가하는 부분 수열, #11055: 가장 큰 증가 부분 수열, #14002: 가장 긴 증가하는 부분 수열 4 문제들과 거의 푸는 방식이 똑같다. 따라서 위에 문제를 아직 안풀어봤다면 복습 한다는 생각으로 위에 문제들도 풀어보기를 바란다.

  ⚠️ #14002: 가장 긴 증가하는 부분 수열 4는 조금 더 어려우니 풀 때 유의하길 바란다.

• 이 문제는 바텀업 방식으로 for문으로 모든 배열을 돌면서 두번째 for문에서 현재 배열보다 큰 이전 값을 찾은 뒤 그 중 배열에 저장 된 길이가 제일 긴 값에에 1을 더해준 뒤 자신의 dp 배열에 저장 해주면 된다. dp 배열에 저장할 때는 최대값을 answer에 기록을 해주어 최종적을 남는 값이 제일 긴 값 이도록 한다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, answer = 0, arr[1000], dp[1000]={};
	//입력
	cin >> n;
	for(int i = 0; i < n; i++){
		int max_length = 0; //이전 최대 길이 없애기 위해 0으로 초기화
		cin >> arr[i];
		//이전 값을 확인하기 위한 for문
		for(int j = 0; j < i; j++){
			//자신 이전에 있는 수 중 자기보다 큰 수 중에 최대 길이를 기록
			if(arr[i] < arr[j]) max_length = max(max_length, dp[j]);
		}
		dp[i] = max_length+1; //기록한 최대 길이에 자기 자신도 포함 되므로 1을 더해준다.
		answer = max(answer, dp[i]); //배열에 저장 된 값중 최대값 기록ㄴ
	}
	//출력
	cout << answer;
}