백준 11722번. 가장 긴 감소하는 부분

백준 11722번. 가장 긴 감소하는 부분

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

유사 문제(가장 긴 증가하는 부분)

거의 똑같다

• 가장 긴 증가하는 부분에서 증가 감소만 반대로 해주면 된다.

5. 처음 코드와 달라진 점

• 가장 긴 증가하는 부분도 100% 직접 푼 게 아니라서 이번에도 좀 헷갈렸다.
• d[0] = arr[0] 같은 멍청한 짓을 해서 문제를 어렵게 만들었다.

6. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1000];
int d[1000];

int main(){	
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++){
		scanf_s("%d", &arr[i]);
		d[i] = 1;
	}
	
	for (int i = 1; i < n; i++){
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[i]) d[i] = max(d[i], d[j] + 1);
		}
	}

	int max_value = d[0];

	for (int i = 1; i < n; i++){
		max_value = max(max_value, d[i]);
	}

	printf("%d", max_value);
}