[백준 / BOJ] 11053번: 가장 긴 증가하는 부분 수열

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

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

 

 

---

 

코드

---

1. 

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	int n, a[1000], dp[1000] = {}, max_idx = 0, max;
	scanf("%d", &n);

	fill_n(dp, n, 1);

	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}

	for (int i = 1; i < n; i++) {
		max = 0;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i] && max < dp[j]) max = dp[j];
		}
		dp[i] = max + 1;
	}

	max = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] > max) max = dp[i];
	}

	printf("%d", max);
	return 0;
}

 

 

 

2.

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	int n, a[1000], dp[1000] = {}, maxlen, res = 1;
	scanf("%d", &n);

	fill_n(dp, n, 1);

	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		maxlen = 0;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i]) dp[i] = max(dp[j]+1, dp[i]);
		}
		res = max(dp[i], res);
	}

	printf("%d", res);
	return 0;
}

---

 

 

입력으로 주어진 수열에서, 반복문을 사용하여 첫번째 수부터 i번째 수까지, i번째 수를 포함하는 증가하는 부분 수열의 최대 길이를 dp[i]에 저장한다. 배열 dp의 값은 수열의 각 숫자마다 적어도 1이므로, 초기값을 1로 초기화한다.

숫자 i에 대해, 첫번째 수부터 i번째 수까지 부분 수열의 최대 길이를 구하는 과정은 다음과 같다.

1. 첫번째 수부터 i-1번째 수까지 검사하여 i번째 수보다 작은 값을 찾는다.
2. i보다 작은 수가 있다면 그 수에서의 (dp값+1)과 dp[i]값을 비교하여 더 큰값을 dp[i]로 둔다.