[백준 / C++] Day89. 가장 긴 감소하는 부분 수열

2024. 08. 31 - 코딩테스트 스터디 Day89

 
 

01. 문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.
 
 

02. 입력

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

03. 출

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

04-1. 예제 입력 1

6
10 30 10 20 20 10

 
 

04-2. 예제 출력 1

3

 

 

4. 풀이 및 답 

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int N;
	cin >> N;

	int A[1000];
	int dp[1000];

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		dp[i] = 1;
	}

	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (A[i] < A[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}

	int result = dp[0];
	for (int i = 1; i < N; i++) {
		result = max(result, dp[i]);
	}

	cout << result;

	return 0;
}

dp 배열을 선언하고 각 요소를 1로 초기화한다. dp에는 배열 A의 i번째 요소를 마지막으로 포함하는 감소하는 부분 수열의 최대 길이를 담는다.
 
중첩 반복문을 사용하여 감소하는 부분 수열의 최대 길이를 찾도록 한다.
A[i]보다 그 왼쪽에 있는 수가 더 크다면 dp[i]와 dp[j]+1를 비교하여 dp[i]에 넣는다.
 
예를 들어, 

6
10 30 10 20 20 10

 
위와 같이 입력 값이 들어왔고, 현재 i가 2인 상태라면
A[i] = A[2] = 10이고,
A[i]보다 왼쪽에 있는 숫자 중 A[i] 값보다 큰 수 30가 A[1]에 존재하기 때문에,
dp[2] = 1과 dp[1] + 1 = 2를 비교하여 더 큰 수인 2를 dp[2]에 넣는다.
 
→ 감소하는 부분 수열(30, 10)을 찾았기 때문에 A의 2번째 요소를 를 마지막으로 포함하는 감소하는 부분 수열의 길이(dp[2])를 갱신한 것이다.
 
마지막으로 dp 배열에서 가장 큰 값을 찾아 출력한다.
 
 

정답!

---