BaekJoon(11053)::가장 긴 증가하는 부분 수열

문제

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

문제 파악

수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

LIS 알고리즘으로 해결이 가능한 문제이다.

문제 풀이

해당문제는 사실 제목에도 적혀있었지만 LIS문제인지 몰랐다...

물론 LIS알고리즘에 대해서 알고는 있지만 너무 오랜만에 접해서 머리속에서 LIS를 떠올리지는 못했다.

 

하지만.... 풀고보니 LIS로 이미 풀었더군요..

#include<iostream>

using namespace std;

int main() {
	int n, sol;
	int nums[1000];
	int dp[10000];

	cin >> n;

	for (int i = 0;i < n;i++) {
		cin >> nums[i];
		dp[i] = 1;
	}

	sol = dp[0];

	for (int i = 1;i < n;i++) {
		for (int j = 0; j < i;j++) {
			dp[i] = (nums[j] < nums[i]) && dp[j] >= dp[i] ? dp[j] + 1 : dp[i];
		}
		sol = (sol < dp[i]) ? dp[i] : sol;
	}

	cout << sol << endl;

	return 0;
}