[C++] LIS & DP / 백준 11053번 - 가장 긴 증가하는 부분 수열

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

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

---

< Solution 1 - Longest Increasing Subsequence >

// Longest Increasing Subsequence
#include <bits/stdc++.h>
using namespace std;

int n;
int A[1005];
int L1[1005];

vector<int> Last;

void LIS(int X[], int D[])
{
	int i;
	vector<int>::iterator it;
	Last.clear();
	Last.push_back(-1);
	for (i = 1; i <= n; i++) {
		if (Last.back() < X[i]) 
			Last.push_back(X[i]);
		it = lower_bound(Last.begin(), Last.end(), X[i]);
		*it = X[i];
		D[i] = it - Last.begin();
	}
}


int main()
{
	int i, cnt = 0, LMax;
	cin >> n;
	for (i = 1; i <= n; i++) {
		cin >> A[i];
	}

	LIS(A, L1);
	L1[0] = -1;	LMax = -1;
	for (i = 1; i <= n; i++) {
		if (L1[i] > LMax)
			cnt++;
		LMax = max(LMax, L1[i]);
	}

	cout << cnt << '\n';

	return 0;
}

---

< Solution 2 - Dynamic Programming >

// Dynamic Programming
#include <bits/stdc++.h>

using namespace std;
int arr[1001];
int dp[1001];

int n;

int main() {
    
    int i, j, val = 0, ans = 0;
    cin >> n;
    for (i = 1; i <= n; i++) cin >> arr[i];

    dp[1] = 1;

    for (i = 2; i <= n; i++) {
        val = 0;

        for (j = 1; j < i; j++) {
            if (arr[j] < arr[i]) {
                if (val < dp[j]) val = dp[j];
            }
        }
        dp[i] = val + 1;
    }

    for (i = 1; i <= n; i++) {
        if (ans < dp[i]) ans = dp[i];
    }
    cout << ans;
}

메모리 면에서 solution 2(dp) 가 더 좋음

 

다 풀었다면 심화문제에 도전 해보도록.

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

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

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

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