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

처음엔 못 풀었다가, 강의를 듣고 나서 풀었다.

길이를 따로 저장하는 dp 배열을 하나 더 추가해서 풀어보니 쉬웠다.

참고로, 이 풀이보다 더 간단한 풀이가 있어서 정답 코드 2개를 올린다.

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

lower_boud 참고 사이트 : http://blockdmask.tistory.com/168

<풀이 1 : 배열 활용>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int A = 0; // 수열의 크기
 
int num[1000 + 1] = { 0, };
 
int dp[1000 + 1] = { 0, };
 
int main(void)
{
    int ans = 0;
 
    scanf("%d", &A);
 
    for (int i = 1; i <= A; i++)
    {
        scanf("%d", &num[i]);
    }
 
    for (int i = 1; i <= A; i++)
    {
        dp[i] = 1; // 각각 숫자 하나 당 길이는 1이다.
 
        for (int j = 1; j < i; j++) // 처음부터 i-1까지는 비교를 한다.
        {
            if (num[i] > num[j] && dp[j] + 1 > dp[i]) // 그 전 숫자보다 당연히 커야 하고, 그 전 숫자의 길이의 합보다 크다면
            {
                dp[i] = dp[j] + 1; // 갱신
            }
        }
 
        ans = max(ans, dp[i]); // 길이 최댓값 저장
    }
 
    printf("%d\n", ans);
 
    return 0;
}
 

<풀이 2 : vector, lower_boud 활용>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int A = 0; // 수열의 크기
 
int num = 0;
 
vector<int> v;
 
int main(void)
{
    int ans = 0;
 
    scanf("%d", &A);
 
 
    scanf("%d", &num);
    
    v.push_back(num);
 
    for (int i = 1; i < A; i++)
    {
        scanf("%d", &num);
 
        if (v.back() < num)
        {
            v.push_back(num);
        }
        else
        {
            auto it = lower_bound(v.begin(), v.end(), num);
 
            *it = num;
        }
    }
 
    cout << v.size() << '\n';
 
    return 0;
}