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

 

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

 

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

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

 

---

 

 

해결전략

 

최대 증가길이 수열

Longest Increasing Subsequence, LIS

Dynamic Programming (DP) 다이나믹 프로그래밍

 

 

---

 

코드

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, res;
	cin >> n;
	vector<int> v(n), dp(n);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	dp[0] = 1;
	res = 1;
	for (int i = 1; i < n; i++) 
	{
		int prevDpMax = 0;

		for (int j = i - 1; j >= 0; j--)
		{
			if (v[j] < v[i] && dp[j] > prevDpMax)
			{
				prevDpMax = dp[j];
			}
		}

		dp[i] = prevDpMax + 1;

		if (res < dp[i]) res = dp[i];
	}

	cout << res;

	return 0;
}

 

 

---

 

코드 해설

 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, res;
	cin >> n;

	//주어진 값을 넣는 v, 각 숫자의 최대부분 증가 길이를 기록하는 dp
	vector<int> v(n), dp(n);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	dp[0] = 1;//첫 숫자의 최대부분 증가 길이는 무조건 1이다.
	res = 1;//n=1인 경우 dp[0]이 최대부분 증가 길이이기 때문에 1이다.

	for (int i = 1; i < n; i++) 
	{
		int prevDpMax = 0;

		// i-1 ~ 0까지 탐색. 
		for (int j = i - 1; j >= 0; j--)
		{
			// v[i]의 숫자보다 작은 숫자들 중 최대부분 증가 길이가 prevDpMax보다 큰 경우
			// max값이 0으로 시작해서 계속해서 큰 값으로 갱신된다. 
			// 결국에 해당 if조건에서 가장 큰 dp[j]값이 prevDpmax값이 된다. 
			if (v[j] < v[i] && dp[j] > prevDpMax)
			{
				prevDpMax = dp[j];
			}
		}

		//dp[i]보다 작은 숫자에서 가질 수 있는 최대부분 증가 길이(위에서 설정한 prevDpMax)에서 +1 해준다. 뒤에 i번째 위치한 숫자를 배치한다는 개념이다.
		dp[i] = prevDpMax + 1;

		//i번째 최대부분 증가 길이가 가장 큰 값인지 검사하고 가장 큰 값이면 res값을 dp[i]로 갱신한다.
		if (res < dp[i]) res = dp[i];
	}

	cout << res;

	return 0;
}

 

 

 

---