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

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

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

 

#include <iostream>
#include <algorithm>
using namespace std;
int a[1001] = { 0, };
int dp[1001] = { 0, };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int n;
	cin >> n;
 
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
 
	int ans = 0;
 
	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = i - 1; j >= 1; j--) {
			if (a[i] > a[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(dp[i], ans);
	}
 
	cout << ans;
 
 
	
	return 0;
}

 

dp로 계산 해야 하는 문제,  dp[i]는 1부터 i까지 가장 긴 증가하는 부분

 

따라서, dp[i]는 전부 1로 초기화 해주고 a[i]가 i - 1부터 1까지 순차적으로 비교하며 

 

만약 a[i]가 더 크다면 dp[i]값과 dp[j] + 1 값 중 더 큰 값을 dp[i]에 저장해준다. 

 

최종적으로 dp[i]값이 계산 되었다면 최대값을 구하기 위한 ans에 간단하게 비교하여 기존값보다 크다면 저장하여 마지막에 출력해준다. 

 

기본적인 아이디어이지만 단시간에 생각해 내긴 좀 어려운 문제였다.