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

https://www.acmicpc.net/problem/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)

 

 

 

 

출력

 

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

 

 

 

 

 

 

이 문제는 11053번 문제와 유사하다.

2020/01/17 - [백준 알고리즘] - 백준 11053번: 가장 긴 증가하는 부분 수열 구하기

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

 

 

 

 

가장 긴 감소하는 부분 수열은 가장 긴 증가하는 부분 수열과 다르게 마지막 숫자부터 계산한다.

 

 

 

 

 

 

코드

 

#include <stdio.h>

int main(){
	int count;
	scanf("%d", &count);

	int seq[1002]; // 수열
	int dp[1002]={ 0, }; // 감소하는 수열 길이
	int tmp; // 감소하는 수열 길이(임시값)
	int max=1;

	// 숫자 입력하기
	for(int i=1; i<=count; i++)
		scanf("%d", &seq[i]);

	dp[count+1]=0; seq[count+1]=0; dp[count]=1;

	for(int i=count-1; i>=0; i--) {
		tmp=0;
		for(int j=i+1; j<=count+1; j++){
			if(seq[i]>seq[j] && (dp[j]+1)>tmp)
				tmp=dp[j]+1;
		}
		dp[i]=tmp;

		if(dp[i]>max) max=dp[i];
	}

	printf("%d\n", max);
}