백준 11053번 가장 긴 증가하는 부분 수열 문제풀이 c++

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

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

문제 해석

이 문제를 처음 봤을때 dp 문제임을 눈치챘으나 아이디어가 떠오르지않아 힌트를 보고 풀었다

수열을 위한 배열 A외에 새로운 배열 B를 추가해준다.

이때 B[i]를 A[i]값을 끝 원소로 가지는 부분 수열중 그 길이가 가장 큰 값이라고 정의를 한다.

그렇게 정의를 하고 나면 수열 A가 10 20 10 30 20 50 이면 배열 B 는 아래와 같은 순서로 값을 가진다.

편의상 A[0]과 B[0]에는 0으로 채워주고 1부터 6까지 사용한다.

1번째

A[1]=10을 끝으로 갖는 수열중 가장 긴 경우는 {10} 길이는 1이므로 B[1]=1

2번째

A[2]=20을 끝으로 갖는 수열중 가장 긴 경우는 {10 20} 길이는 2이므로 B[2]=2

3번째

A[3]=10을 끝으로 갖는 수열중 가장 긴 경우는 {10} 길이는 1이므로 B[3]=1

4번째

A[4]=30을 끝으로 갖는 수열중 가장 긴 경우는 {10 20 30} 길이는 3이므로 B[4]=3

5번째

A[5]=20을 끝으로 갖는 수열중 가장 긴 경우는 {10 20} 길이는 2이므로 B[5]=2

6번째

A[6]=50을 끝으로 갖는 수열중 가장 긴 경우는 {10 20 30 50} 길이는 4이므로 B[6]=4

n이 1000까지 제한되어 이중 for문으로 n번 반복하면 n의 제곱으로도 푸는것이 가능하다.

j를 0~i-1인 변수로 두고 조건식을

현재 A[i]가 A[j] 보다 큰 값이면 B[j]+1을 모아 뒀다가 그들중 가장 긴값이 B[i]가 되게끔 코드를 짰다.

길이와 끝수를 동시에 표현하고 사용하기위해 pair를 사용하였고

소팅을 사용한 이유는 마지막에 가장 긴 길이를 출력해야하기 위함도 있고

다음 글에서 설명할 백준 14002번 가장 긴 증가하는 부분 수열 4 을 풀때 사용하기 위함도 있다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
vector < pair<int,int> > v; //길이,끝수
void solve();
int a[1001];
int n;
int ans=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    solve();
}
void solve(){
    v.push_back({0,0});
    for(int i=1; i<=n; i++)
    {
        int mx=0;
        for(int j=0; j<i; j++)
        {
            if(a[j]<a[i])
            {
                mx=max(mx,1+v[j].first);
            }
        }
        v.push_back({mx,a[i]});
    }
    sort(v.begin(),v.end());
    cout<<v[v.size()-1].first;
}