[백준] 11053번. 가장 긴 증가하는 부분 수열

leeeha·2022년 8월 3일

백준

목록 보기

60/166

문제

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

출력

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

예제

풀이

오답

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

int main() {
  	ios::sync_with_stdio(0);
  	cin.tie(0);

	int N; 
	cin >> N; 

	vector<int> arr; 
	for(int i = 0; i < N; i++){
		int x; 
		cin >> x; 
		arr.push_back(x); 
	}

	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end()); 

	cout << arr.size();  
	
  	return 0;
}

입력 받은 배열을 오름차순으로 정렬하고 중복되는 원소들을 삭제하면, 가장 긴 증가하는 부분 수열이 나오는 줄 알았다. 그런데 오답이다!

그 이유는 부분 수열은 기존 수열로부터 구할 수 있어야 하는데, 정렬을 통해 원소들의 순서를 마음대로 바꿔버리면 기존 수열로부터 절대 나올 수 없는 부분 수열이 정답으로 출력될 수도 있기 때문이다.

DP

참고: https://tjdahr25.tistory.com/18

문제의 예시로 나온 A = {10, 20, 10, 30, 20, 50} 수열을 통해 점화식을 도출해보자.

dp[i]에는 i번째 항 앞쪽 (0 ~ i-1)에 있는 i번째 항보다 작은 수들 중에서, dp 테이블의 최댓값에 1을 더한 값을 저장하면 된다. 만약 자신의 앞쪽에 자신보다 작은 수가 없다면, 자기 자신만 가장 긴 증가하는 부분 수열이므로 길이는 1이다.

이렇게 dp 테이블에 값을 저장하고, 그 중에서 최댓값이 가장 긴 증가하는 부분 수열의 길이가 된다.

arr[0]의 앞쪽에 다른 수가 없으므로 dp[0] = 1

arr[1]의 앞쪽에 20보다 작은 수 10이 있으므로, 그 dp 테이블의 값에 1을 더하면 dp[1] = 2

arr[2]의 앞쪽에 10보다 작은 수가 없으므로, dp[2] = 1

arr[3]의 앞쪽에 30보다 작은 수는 10과 20이고 dp[1] = 2가 최대이므로 거기에 1을 더하면, dp[3] = 3

arr[4]의 앞쪽에 20보다 작은 수는 10이므로, dp[4] = 2

arr[5]의 앞쪽에 50보다 작은 수는 10, 20, 30인데 그 중에서 dp[3] = 3이 최대이므로 거기에 1을 더하면, dp[4] = 4

dp 테이블에서 최댓값인 4가 가장 긴 증가하는 부분 수열의 길이가 된다.

C++ 코드

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 1001; 
int arr[MAX]; 
int dp[MAX]; 
int maxLength = 0; 

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

	for (int i = 0; i < N; i++) {
		int tmp = 0;

		// i보다 앞쪽에 있으면서  
		for (int j = 0; j < i; j++) {
			// i번째 값보다 작은 원소들 중에 
			if (arr[j] < arr[i]) {
				// dp 테이블의 최댓값 구하기 
				tmp = max(tmp, dp[j]);
			}
		}

		dp[i] = tmp + 1; // 거기에 1을 더해서 dp 테이블 갱신 
		maxLength = max(dp[i], maxLength); // dp 테이블의 최댓값 갱신 
	}

	cout << maxLength; 

	return 0;
}