백준 11053문제.

가장 긴 증가하는 부분 수열

 

---

Problem?

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

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

DP?

 

Input

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

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

 

Output

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

 

Solution

위 문제는 몇 가지 특징이 있다.

아래에서 보는 코드를 보면, 해당 배열은 항상 새로운 input이 들어와도 가장 큰 부분 수열의 사이즈를 들고 있음을 확인할 수 있다.

숫자를 입력받으면, 그전까지 입력받은 숫자보다 작은 수들 중에서 가장 왼쪽에 있는 자리의 위치를 찾아 그 위치와 바꾼다.(이 경우는 사이즈를 늘리지 않음, 작은 수가 없는 경우는 사이즈를 늘린다.)

그리고 해당 사이즈를 비교해가며 input을 늘려나가면 문제를 풀어나갈 수 있다.

 

가정 A : 숫자 배열 find_i : 내가 찾고자 하는 위치(바꿀 위치)

Code

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

int main() {
	int N, num;
	int find_i, size = 0;
	int A[1000];

	cin >> N;

	scanf("%d", &num);
	A[0] = num;
	size++;

	for (int i = 1; i < N; i++) {
		scanf("%d", &num);
		find_i = size;
		for (int j = size - 1; j >= 0; j--) {
			if (A[j] >= num) {
				find_i = j;
			}
		}
		A[find_i] = num;
		if (find_i != size)
			size--;
		size++;
	}

	cout << size << "\n";

	return 0;
}

 

---

아이디어를 생각하는데 조금 걸리는 시간.

 

자료구조로 어려웠던 점은 없는 문제.