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

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, maxNum = 0;
vector<pair<int, int>> num;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int temp;
		cin >> temp;
		num.push_back({temp, 1});
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (num[j].first < num[i].first)
			{
				num[i].second = max(num[i].second, num[j].second + 1);
			}
		}
		maxNum = max(maxNum, num[i].second);
	}

	cout << maxNum;
}

풀이

1. 처음 수와 그 다음 수의 크기를 비교해서 작으면 if문

2. 그 값 j의 최대 수열 + 1과 현재 값을 비교해서 그 값 j를 i값에 넣는다.

 

ex)

 

1  2  1  3

1  1  1  1

1 < 2

2 = max(1, 1+1)

 

1  2  1  3

1  2  1  1

1 < 1

X

 

1  2  1  3

1  2  1  1

1 < 3

2 = max(1, 1+1)

 

1  2  1  3

1  2  1  2

2 < 3

3 = max(2, 2+1)

 

1  2  1  3

1  2  1  3

1 < 3

3 = max(3, 1+1)

 

maxNumber = max(maxNumber, 3)

 

이런식으로 값이 비교하면서 쌓이게되고 큰 수를 정한다.