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

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

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

---

문제 접근

 배열 arr은 입력받은 값을 저장하는 배열이고 DP는 특정 값이 최대 위치인 길이를 저장한다. 

입력받은 값들을 비교하는데 변수 idx는 arr[i]의 값이 위치할 수 있는 인덱스 넘버를 저장한다. 

두 값을 비교하고 타겟(arr[i])이 더 크다면 위치값을 올려준다. 

여기서 MAX 함수로 기존 idx 값과, DP[j]을 비교해서 더 큰 값으로 업데이트한다. 

업데이트가 끝났다면 DP[i]에 idx + 1 의 값을 저장해준다. +1을 하는 이유는 길이이기 때문이다.

느낀점

 연속되는 스리즈의 문제들이다. 자주 출제되고 대표적인 문제라고 해서 여러번 곱 씹어서 이해했다. 이번 기회로 알고리즘마다 따로 공부해서 정리해야겠다.

코드

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

int n, ans = 0;
int arr[1001], dp[1001];

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> arr[i];
		int idx = 0;
		for (int j = 0;j < i;j++) {
			if (arr[i] > arr[j]) {
				idx = max(idx, dp[j]);
			}
		}
		dp[i] = idx + 1;
		ans = max(ans, dp[i]);
	}

	cout << ans;
}