[백준] 11053번: 가장 긴 증가하는 부분 수열 풀이 및 해설(C++)

문제 이미지

풀이

입력된 수열들을 arr []에 저장한다.

다이내믹 프로그래밍으로 dp [n]에 n번째 원소를 마지막으로 취할 때의 길이를 저장한다.

그리고 dp 배열에서 최댓값을 찾으면 된다.

 

그러면 dp[n]은 어떻게 찾을 수 있을까?

입력을 받을때마다, 이전 배열값들을 탐색한다.

n> m일 때, arr [m]<arr [n]을 만족하는 dp [m]중 가장 큰 값에 1을 더한다.

 

 

 

해답 코드

#include <iostream>
#include <string>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n,max=1,beforemax;
    cin>>n;
    int arr[n];
    int dp[n];
    cin>>arr[0];
    dp[0]=1;
    for(int i=1; i<n; i++){
        cin>>arr[i];
        beforemax=0;
        for(int j=0; j<i; j++){
            if(arr[j]<arr[i] && beforemax<dp[j]){
                beforemax=dp[j];
                //이전배열을 탐색중인 상태에서 현재의 최댓값 저장
            }
        }
        dp[i]=beforemax+1;
        if(dp[i]>max){
            max=dp[i];
        }
    }
    cout<<max;

    
    return 0;
}

해맸던 부분

예전에 틀렸던 기록을 보니, 태초에 beforemax를 0이 아닌 1로 저장해서 틀렸다.

이렇게 하면 모든 값이 동일한 수열 가령 10 10 10 같은 수열에서 오답을 내놓는다.