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

 

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

 

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

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

---

 

 

해결전략

 

최대 증가길이 수열

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;
}

 

 

 

---