백준 11053 가장 긴 증가하는 수열(C++)

 처음 봤을 땐

 

"엥? 이거그냥 중복하면 받지말고 나중에 벡터 사이즈 넣으면 끝인데?" 라고 생각했다.

 

그런데 정답률이 낮아서 의아했다. 

그리고 당연히 그런 문제가 아니었다. 이 문제의 가장 중요한 건 문제 해석을 완벽히 해야한다.. 이 문제의 이름을 잘 보자

" 가장 긴 -증가하는- 수열 "

 

그러니까 예를들어 5 4 3 2 1 이라는 순서로 들어왔을 때 그냥 1 2 3 4 5라고 생각할 수 있지만 이 문제는 "수열" 이다. 순서를 절대 바꾸면 안된다. 그러므로 증가하는 부분 수열의 길이는 1이다. 이 문제는 들어오는 숫자가 과연 증가하는 수열을 만들수 있는가? 물어보는 문제이다.

---

• 예를 들어보자!

5 2 4 3 2 순으로 들어왔다고 가정하자. 

 

1) 5가 들어왔을 때 -> 아무것도 없고 처음이므로 증가 하는 부분 수열은 1이다. DP[5] = 1

2) 2가 들어왔을 때 -> 5가 있지만 5 ,2 는 증가 수열이 아니므로 DP[2] = 1

3) 4이 들어왔을 때 -> 5 2 4 에서 4보다 작은 수가 1개 있으므로 DP[4] = 2

4) 3이 들어왔을 때 -> 5 2 4 3 에서 3보다 작은 수는 1개 있으므로 DP[3] = 2

5) 2가 들어왔을 때 -> 5 2 4 3 2 에서 2보다 작은 수는 1개 있으므로 DP[2] = 1

 

그러므로 여기서 가장 긴 증가하는 수열은 2가 된다. 

여기서 DP 갱신 조건은 원소 A가 들어오고 인덱스 0부터 살펴봤을 때 A보다 작은 게 있다면 DP + 1 을 해주면 된다.

 

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

int main() {
	int n, m;
	int DP[1001] = { 0, };
	vector<int> vec;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> m;
		vec.push_back(m);
		DP[m] = 1;
	}
	int answer = 0;
	for (int i = 0; i < vec.size(); i++) {
		for (int j = 0; j < i; j++) {
			if (vec[i] > vec[j]) {
				DP[vec[i]] = max(DP[vec[j]] + 1, DP[vec[i]]);
			}
		}
		answer = max(answer, DP[vec[i]]);
	}

	cout << answer << endl;
}