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

Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열]

---

 문제 

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

11053번: 가장 긴 증가하는 부분 수열

---

 설명 

  Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다.

 

 

  정답을 구하기 위해서 arr 의 첫 번째 수 부터 list 배열을 활용하여 가장 긴 증가하는 부분수열을 구하기 위한 Memoization 을 시작한다.

 

 

  전체적인 흐름은 문제의 의도를 반영하여 흐른다. 가장 긴 증가하는 부분수열의 크기를 구해야 하므로 arr 배열을 순서대로 확인을 하면서, list 배열에서 가장 긴 증가하는 부분수열의 크기를 파악할 수 있게끔 list 배열을 계속해서 update 를 진행 할 것 이다. 이제 arr 에서 다음 수인 4를 넣는다.

 

 

  4는 현재 list 의 가장 마지막 값 (현재 list 에서의 최대값) 보다 크므로 list 의 가장 끝쪽에 추가된다. 이제 arr 에서 다음 수인 5를 추가한다.

 

 

  5도 마찬가지로 현재 list 의 가장 마지막 값 (현재 list 에서의 최대값) 인 4보다 크므로 list 의 가장 끝쪽에 추가가 된다. 이제 arr 에서 다음 수인 2를 추가한다.

 

 

  2는 현재 list 의 최대값인 5보다 작다. 따라서 지금까지와 같이 그냥 list 의 우측에 삽입하지 않는다. 이 경우엔 현재 arr 의 값인 2가 최대한 좌측에 위치하게 된다. 최대한 좌측에 위치하는 조건은, 현재 list 에서 본인보다 작은 값들 중 가장 큰 값이 바로 좌측에 위치하는 것이다. list 에서 현재 값의 lower_bound 에 해당되는 위치에 들어가게 된다.

  그러면, 그렇게 2가 list 에 자리잡은 후 list 을 보면 현재 arr 에서 증가하는 부분수열에 해당이 되지 않는다. 하지만 이 문제에서 요구하는 것은 결국 증가하는 부분 수열 중 가장 긴 수열의 크기이므로 이 문제는 중요하지 않다.

  4가 위치하던 자리에 굳이 2를 넣는 이유는? list 에 해당되는 숫자들의 크기가 계속해서 최대한 작게 업데이트가 되어야 이후 list 에 대입이 될 수들이 정상적으로 대입이 되기 때문이다. 1 -> 4 -> ... 보다 1 -> 2 -> ... 가 당연하게 이후 증가수열을 오류없이 판단할 수 있다.

 

 

  3은 현재 list 의 최대값보다 작다. 따라서 2와 마찬가지로 list 의 끝에 위치하는 것이 아닌 list 의 내부에서 lower_bound 에 해당되는 수와 swap 을 해야한다. 따라서 3은 현재 list 의 5의 값과 swap 이 되었다.

 

 

  arr 에서 마지막으로 5가 추가가 되었다. 이는 현재 list 의 최대값이었던 3보다 크므로 list 의 가장 마지막에 push 되었다. 

 

 

  그 결과, list 는 위와 같이 정의가 되었다. arr 에서 파란 부분들이 list 에 대입이 되어 있는 상태이다. 위와 같은 경우는 우연찮게 arr 에서 가장 긴 증가하는 부분 수열이 list 에 대입이 되었다. 하지만 이는 말 그대로 우연일 뿐이다. 마지막 3, 5 숫자가 arr 에서 없다면, list 에는 {1, 2, 5} 가 대입이 되어있었을 것 이다.

  문제에서 요구하는 가장 긴 증가하는 부분 수열의 길이는 list 배열의 size 가 된다.

 

  입력 조건은 위와 같은 크기이므로, arr 배열과 list 배열은 short type 으로 선언해도 문제없다.

---

 Code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<short> arr;
vector<short> list;

int main() {
	// arr를 입력 받는다.
	cin >> n;
	arr.assign(n + 1, 0);
	list.assign(1, -20000);

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];

		if (list[list.size() - 1] < arr[i]) { // 현재 입력된 수가 지금 list에서의 가장 우측의 최대값보다 큰 경우
			list.push_back(arr[i]); // list 의 우측에 삽입한다.
		}
		else { // 그렇지 않은 경우
			   // 현재 숫자 크기 이상의 숫자가 나오는 list 에서의 index를 탐색
			int inputIndex = lower_bound(list.begin(), list.end(), arr[i]) - list.begin();
			list[inputIndex] = arr[i]; // 탐색한 index 에 현재의 수를 대입
		}
	}

	cout << list.size() - 1; // list[0]는 사용하지 않고 list[1] 이후로만 사용이 되므로
							 //   list 의 size 보다 1 작은 값을 출력
}