[C/C++] BOJ 11053 :: 가장 긴 증가하는 부분 수열

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

문제 링크 : https://www.acmicpc.net/problem/11053

나는 아직 for문 여러 개를 사용해서 다이나믹 프로그래밍 하는 것에 서툰 것 같다!!

옛날에 살짝 공부했던 적이 있는 LIS 기초 부분인데도 제대로 풀지 못했다 ㅠㅠ..

알고리즘에 대한 공부를 명확히 하고 문제를 다시 풀어봐야 겠다!!

나의 풀이

1. 배열의 기준점을 두번째 index에서 가장 긴 곳까지 두면서 비교한다.

2. 배열의 0번에서 기준점까지 점진적으로 비교하면서 증가하는 수열이 될 때에 dp배열을 갱신시킨다.

3. 모든 dp배열을 채운 후, 그 중 가장 큰 값을 찾아 출력한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11053/BOJ_11053.cpp

// 백준알고리즘 11053번 :: 가장 긴 증가하는 부분 수열
#include<iostream>
#include<string.h>
#define max(a , b) (a > b) ? a : b
int N, ans;
int arr[1001];
int dp[1001];
using namespace std;
int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		dp[i] = 1;
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			// 뒤가 더 크면 증가하는 수열이다. 길이를 갱신한다.
			if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	ans = dp[0];
	for (int i = 0; i < N-1; i++)
	{
		if (ans < dp[i + 1]) ans = dp[i + 1];
	}
	cout << ans;
	return 0;
}