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

https://www.acmicpc.net/problem/11053

---

해설

이번 문제는 흔히 LIS 라고 불리는 가장 긴 증가하는 부분 수열 문제이다.

 

예제인 10, 20, 10, 30, 20, 50으로 풀이를 해보겠다.

일단, 여기서의 답은 10,20,30,50 으로 4이다.

 

	10	20	10	30	20	50
1번	1
2 "	1	2
3 "	1	2	1
4 "	1	2	1	3
5 "	1	2	1	3	2
6 "	1	2	1	3	2	4

 

이것만 보면 이해가 되겠는 가?

이제 천천히 설명해보겠다.

 

1번은 첫번째인 10까지의 부분 수열이 얼마나 나오는 지 구하는 건데, 1번은 10만 비교하니 1이다.

2번은 20까지 부분 수열을 구해보는 건데, 10, 20 총 2이다.

3번은 10까지 부분 수열을 구하는 건데, 10 총 1이다.

4번은 30까지 10,20,30 총 3이다.

5번은 20까지 총 2이다

6번은 50까지 총 4이다.

 

여기서 답은 4가 된다.

위 처럼 작동이 된다.

 

이중 for문을 돌린 건데, 

간단하게 설명하면, 처음에 dp[i]를 1로 초기화 시켜 놓는다.

for문으로 i번째 전까지 dp에 적혀있는 수(여기서 dp[j]는 j까지의 가장 긴 수열의 길이가 저장돼 있다.)로 dp[j]+1 (여기서 +1은 자기 자신) 이

자기(dp[i])보다 크고, 그 j의 수가 자기 자신 i 수 작으면(j가 i보다 작아야 증가하는 수열이다.) 그 큰수로 dp 교체해준다.

 

if (num[j] < num[i]) dp[i] = max(dp[i], dp[j] + 1);

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];
int num[1001];
int main() {
	int n; cin >> n;
    
	for (int i = 0; i < n; i++)
		cin >> num[i];
	int res = -1;
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++)
			if (num[j] < num[i])
				dp[i] = max(dp[i], dp[j] + 1);
		res = max(res, dp[i]);
	}
	cout << res << '\n';
}