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

문제 링크

www.acmicpc.net/problem/11053

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

문제 접근

// [백준 11053 c++ V] 가장 긴 증가하는 부분 수열
// 문제: 가장 긴 증가하는 부분수열(오름차순의 부분수열)의 길이를 구하는 문제
// 접근1: 브루트포스로 큰 수 나올 때마다 카운트해서 최대값 찾으려 생각-> 시간초과 예상으로 안함
// 점근2: dp를 이용해 각 자리마다 나오는 증가하는 부분수열의 최대값 저장 

문제 풀이

// 풀이: 1일때는 모두가 1이므로 각 초기 dp[i]는 1
// 처음 인덱스부터 현재검사하는 인덱스 까지 현재검사하는 원소값보다 작으면 dp값 비교해서 최대값으로 최신화
// 계속 최신화 하며 현재 검사하는 인덳까지 가면 dp 값이 곧 부분수열의 길이랑 같음

주의

 

 

개념

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 11053 c++ V] 가장 긴 증가하는 부분 수열
// 문제: 가장 긴 증가하는 부분수열(오름차순의 부분수열)의 길이를 구하는 문제
// 접근1: 브루트포스로 큰 수 나올 때마다 카운트해서 최대값 찾으려 생각-> 시간초과 예상으로 안함
// 점근2: dp를 이용해 각 자리마다 나오는 증가하는 부분수열의 최대값 저장 
// 풀이: 1일때는 모두가 1이므로 각 초기 dp[i]는 1
// 처음 인덱스부터 현재검사하는 인덱스 까지 현재검사하는 원소값보다 작으면 dp값 비교해서 최대값으로 최신화
// 계속 최신화 하며 현재 검사하는 인덳까지 가면 dp 값이 곧 부분수열의 길이랑 같음
using namespace std; // cin,cout 편하게 사용 라이브러리 
#define MAX 1001

int n;
int dp[MAX];
int ar[MAX];

int main()
{
	// IO 속도 향상
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);// 입출력 시간 단축
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
	}

	int max_len = 0;
	for (int i = 0; i < n; i++) {
		dp[i] = 1; // 길이가 1 일때는 모두 1
		for (int j = 0; j < i; j++) {
			if (ar[i] > ar[j]) // i번째 수보다 작으면서
			{
				dp[i] = max(dp[i], dp[j] + 1); // dp 값 비교해서 큰 값 최신화
			}
		}
		max_len = max(max_len, dp[i]);
	}

	cout << max_len;
	

	return 0;
}