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

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

 

혼자 풀어내지 못한 문제.

이중 for문을 쓰는것 외에는 푸는 방법이 떠오르지 않았는데, 시간복잡도에 중점을 두는 DP문제라서 이중 for문이 쓰이진 않을것 같았고, LIS문제라고 하니 처음 들어보지만 정형화된 알고리즘이 있을것 같아서 오래 고민 안하고 다른 풀이를 봤다.

 

---

풀이

LIS문제.

현재수가 이전의 수보다 크면 이전의 수의 길이값을 +1 해준다.

현재수보다 작은 이전의 수가 여러개라면 이전의 수의 길이값들 중 가장 큰것을 선택하고 +1해준다.

 

seq[0] = 0, seq는 입력받은 수, dp는 현재까지 수열의 최대 길이

 

	1	2	3	4	5	6
seq	10	20	10	30	20	50
dp	1	0	0	0	0	0

 

seq[1] 10은 이전의 수 seq[0]보다 크므로 dp[1] = dp[0]+1해준다.

 

	1	2	3	4	5	6
seq	10	20	10	30	20	50
dp	1	2	0	0	0	0

 

seq[2] 20은 seq[0,1]보다 크므로 dp[2]는 dp[0,1]중 최대값(dp[1])에 +1해준다.

 

	1	2	3	4	5	6
seq	10	20	10	30	20	50
dp	1	2	1	0	0	0

 

seq[3] 이전의 수들 중 seq[3]보다 작은것은 seq[0] 뿐이므로 dp[0]+1해준다.

위 과정을 6번째 수까지 반복하면

 

	1	2	3	4	5	6
seq	10	20	10	30	20	50
dp	1	2	1	3	2	4

 

위의 dp값들 중 최대값을 출력한다.

 

---

구현

//c++

#include <iostream>

using namespace std;

int dp[1002];
int seq[1002];

int main() {
	int result = 0;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> seq[i];
		for (int j = 0; j < i; j++) {
			if (seq[j] < seq[i]) {
				if (dp[j] >= dp[i]) {
					dp[i] = dp[j] + 1;
					if (dp[i] >= result) result = dp[i];
				}
			}
		}
	}
	cout << result;

}