[c++] 백준 11053 가장 긴 증가하는 부분 수열 : DP

 

문제

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

 

문제 분석

음 분석이라기 보다는 디피인거 스포당해서;;;

처음에는 그냥 thisSum totalSum 이용해서 풀었는데(올라가다가 꺾이면 totalSum을 update 하는 방식-> 한번만 훑으면 됨) 어차피 틀린 매커니즘이라 자세한 설명은 생략. 저 방식의 문제는 다음과 같은 테케를 해결하지 못한다.

 

8
1 8 9 9 9 2 3 4

 

이 경우 위와같은 방식으로 구하면 1,8,9 이렇게 하고 3이 나오는데,

사실 1,2,3,4 이렇게 증가하면 4가  된다. 

 

즉 1->8 이렇게 가야할지 1->2 이렇게 가야할지 모르니까 다 확인해봐야함..... -> 근데 반복적으로 필요한 값이 있으니 매번 계산하지 않고 기록해뒀다가 이후에도 이용하겠다 -> DP 이용 

 

DP로 풀기

자신까지 봤을때 가장 긴 수열의 크기를 저장하는 배열을 하나 만들고(이하 dp 배열이라 칭함),

나보다 이전에 있는 숫자들을 쭈우욱 살펴보면서 나보다 작은 숫자들 중 수열의 크기가 가장 큰거에 +1 해서 dp배열에 저장하면 된다. 

 

위의 테케로 예를 들면

우선 기본이 되는 0은 먼저 넣어주고 0부터 n번째 인덱스까지 사용할것이다. 

idx 1  일 때 :  num[1] = 1 이니까 인덱스 0을 살펴본다. 다른 살펴볼건 없으니 그냥 바로 dp[0]+1해서 dp[1]은 1.

 

idx 2 일 떄 : idx 1일때 0일 때 둘 다 살펴본다. 둘다 숫자가 나보다 작으니 그 중 dp값이 큰 dp[1]을 가져와서 +1 해준수 dp[2]에 저장.

idx 3일때도 마찬가지로 dix 2,1,0 세개 살펴보고 그중 dp max값에 +1 해서 dp[3]dp 저장한다. 

이런식으로 진행하면 idx 4,5일때 모두 dix 2에서 가져올것이다. 

 

나머지도 살펴보면 다음과 같다.

 

 

정답코드

1. DP로 풀기

#include<iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int num[1001]; int dp[1001];
    num[0]=0; dp[0]=0;
    
    int n; cin>>n;
    int ret=0;

    for(int i=1;i<=n;i++){
        cin>>num[i];
        int m=0;//max
        for(int j=i-1;j>=0;j--){
            if(num[j]<num[i]){
                m=max(m,dp[j]);
            }
        }
        dp[i]=m+1;
        ret=max(dp[i],ret);
    }
    cout<<ret<<endl;
}

간단하게 이중for문으로 구현했다.

근데 신박한 방법으로 푸는 방법이 있다. 

 

2. lower_bound 이용

와 이거 보고 진짜 충격 먹었는데 

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef vector<int> vi;

int main(){
    FASTIO

    int n;cin>>n;
    vi vec(n);
    for(int i = 0 ; i < n ; i++)
        cin >> vec[i];
    vi res;
    for(int i = 0 ; i < n ; i ++){
        auto it = lower_bound(res.begin(), res.end(), vec[i]);
        if(it == res.end()) res.push_back(vec[i]);
        else *it = vec[i];
    }
    cout << res.size();

}

ret 벡터를 만들어서 그 안에 자기보다 같거나 큰거 있으면 그거 대신 자기를 넣고, 없으면 자기 자신을 넣는데

-> 앞에서 얘기한 1 8 9 9 9 2 3 4 이런경우 1에서 9로 가야할지 2로 가야할지 알수 없을때 처음에는 9가 Ret 배열에 있다가 작은값인 2로 대체되면서 이후에 다시 오름차순이 진행될 경우도 카운트 할 수있도록 함. 작은 숫자들이 앞에 많이 있어야 오름차순을 최대한 길게 배열할수 있으니까. 

와 진짜 이거 생각한사람 천재냐 

글로 설명하려니까 읽는 사람이 이해가 되려는지는 모르겠지만 그리기는 귀찮......