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

1. 문제

---

---

2. 문제 분석

• 알고리즘 분류 : 다이나믹 프로그래밍

=> 점화식 / 이전에 구한 값으로 이번 값을 구한다

 

이 문제를 시작할 때 헷갈렸던 것이 "가장 긴 증가하는 부분 수열" 이라는 말의 뜻이다.

본래 수열은 이전 값과 크거나 같은 값도 포함하여 증가하는 수열인데, 여기서 정의한 "증가하는 부분 수열"은

중간에 작거나 같은 값이 있으면 이걸 제외하고, 나머지 증가하는 부분만 따서 길이를 나타낸 것이다.

 

예를 들어,

ex) 70 30 50 60 40 80 10 가 주어졌다면,

 

2번째 줄의 30부터 

30 50 60 80 만 따서 증가하는 부분 수열로 보는 것이다.

---

3. 풀이

주어진 입력의 크기가 1000으로 크지 않지만,

시간이 1초로 짧으므로 2중 for문으로 일일이 비교하는 것은 시간초과로 비효율적이다.

 

또한, 처음부터 세서 제일 작은 값부터 비교하여 다음에 나오는 값이 더 크면

그 값으로 계속 비교하는 풀이도

틀린 풀이이다.

 

ex) 322 831 212 232 545 698 260 265 324 215 701 75 156 605 851 993 425 887 691 593

=> 212 232 260 265 324 605 851 993 순으로 증가하는 수열이 가장 큰 수열.

 

 

 

그렇다면 어떻게 풀 것인가?

🔔 이 문제에서의 dp는 
내가 현재 보고 있는 지점을 기준으로, 이전 지점까지 가장 긴 증가하는 부분 수열의 길이를 통해 구한다.

 

이 풀이 이미지는 아래 링크의 풀이 이미지를 모티브로 제작한 것입니다.

https://hwan-shell.tistory.com/299

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

 

 

 

이런 식의 풀이로 계속해서 비교해나가면 됩니다 !

4. Code

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

vector<int> arr;
vector<int> dp;
priority_queue<int, vector<int>> Q;

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;

	dp.assign(n, 1);

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

	int check = 0;
	int count = 1;

	for (int i = 0; i < n; i++)
	{
		count = 0;
		check = arr[i];

		for (int j = 0; j < i; j++)
		{
			if (arr[j] < check)
			{
				if(count < dp[j])
				count = dp[j];
			}
		}

		dp[i] = count + 1;
	}

	cout << *max_element(dp.begin(), dp.end());
}