백준11722(가장긴감소하는부분수열)

jh Seo·2024년 6월 19일

다이나믹 프로그래밍 백준 한번에 푼 문제

백준

목록 보기

183/194

개요

백준 11722

문제
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

접근 방식

첫번째 방식(맞음)

예전에 푼 문제와 비슷하다. 가장 긴 증가하는 부분수열 문제였는 데
dp방식으로 풀 수 있지만 더 간단하게 vector을 이용해 풀었다.
값을 arr 배열에 받아오고, dp라는 이름의 vector을 선언해준다.
arr을 순회하며 arr[i]가 dp의 마지막 원소보다 작다면 dp에 넣어준다.
arr[i]가 dp의 마지막 원소보다 크다면 dp를 순회한다.
dp의 원소중 arr[i]보다 작은 값중 제일 큰 수를 교체해준다.

ex) dp = {30, 20, 10} , arr[i]=40
dp = {40,20,10}
이렇게 하는 이유는 뒤에 더 큰 수로 시작하는 더 긴 부분수열이 나올 수 있기 때문이다.
ex ) 30 20 10 40 30 10 5
1. 이런 수열에서 dp는 30 20 10 을 저장한 상태고, 일단 10까지 봤을 때 제일 긴 부분 수열이 30 20 10 이다.
2. 위 메커니즘대로 하면
  40이 30의 위치로 들어가고 dp = 40 20 10
  30이 20의 위치로 들어가고 dp = 40 30 10
  10은 10과 같으므로 pass, dp = 40 30 10
  5는 dp의 마지막 원소보다 작으므로 push된다. dp = 40 30 10 5
3. 제일 긴 감소하는 부분수열을 찾았다/
만약 30 20 10 40 30 이렇게 들어와도 제일 긴 감소하는 부분수열은 찾아진다.
40 과 30만 교체하면 되므로 제일 긴 부분수열의 길이는 교체전과 교체후는 동일하기 때문.

두번째 방식 dp (맞음)

dp[i]에 저장된 값은 i를 포함한 수열중 제일 긴 수열의 길이를 저장했다.
0부터 i-1까지 범위인 인덱스 j를 순회시킨다.
arr[j]가 arr[i] 보다 큰 숫자일 때, dp[j]중에서
제일 큰 dp값을 구해주고 dp[i] = 해당 dp값 +1

전체 코드

#include<iostream>
#include<vector>
using namespace std;
vector<int> dp;
int arr[1001];
int N;

int main(){
    cin>>N;

    for(int i=0;i<N;i++){
        cin>>arr[i];
    }    

    // 핵심 논리
    // arr을 순회하며 현재 arr[i]값이 dp의 마지막 값보다 작다면 push
    //dp의 마지막 값보다 크면 dp에서 arr[i]보다 작은 수 중 제일 큰 수를 교체 함
    // ex 30 20 10 에 40이 들어올 차례라면 30이 40보다 작은 수중 제일 큰수 -> 40 20 10
    //이유는 20 10 40 30 10 이런 수열에서 dp가 30 20 으로 구성되어있다가 더 큰 수가 오면 앞부분을 변경해줘야 원활하게 40 30 값이 들어옴
    for( int i=0;i<N;i++){
        if(dp.empty() || dp.back() > arr[i])
        {
            dp.push_back(arr[i]);
            continue;
        }
        else if(dp.back() < arr[i]){
            for(int j=0;j<dp.size();j++){
                if( dp[j]> arr[i]) continue;
                dp[j]=arr[i];
                break;
            }
        }

    }
    cout<<dp.size();
}

전체 코드(dp방식 풀이)


#include<iostream>
#include<vector>
using namespace std;
int dp[1002];
int arr[1001];
int N;

int main(){
    cin>>N;

    for(int i=0;i<N;i++){
        cin>>arr[i];
    }    
    fill(&dp[0],&dp[1001],1);
    int maxLength=1;

    for( int i=0;i<N;i++){
        int maxj=-1,maxjAmount=-1;
        for(int j=0;j<i;j++){
            if(arr[i]< arr[j]){
                if(maxjAmount < dp[j]){
                    maxj=j;
                    maxjAmount=dp[j];
                }
            }

        }
        if(maxj!=-1){
            dp[i] =dp[maxj]+1;   
            maxLength= dp[i]>maxLength? dp[i]:maxLength;
        }
    }
    cout<< maxLength;

    
}

전체코드(dp풀이 코드단축)

#include<iostream>
#include<vector>
using namespace std;
int dp[1002];
int arr[1001];
int N;

int main(){
    cin>>N;

    for(int i=0;i<N;i++){
        cin>>arr[i];
    }    
    fill(&dp[0],&dp[1001],1);
    int maxLength=1;

    for( int i=0;i<N;i++){

        for(int j=0;j<i;j++){
            if(arr[i]< arr[j]){
                dp[i] = max(dp[j]+1, dp[i]);
            }

        }
        maxLength= max(dp[i],maxLength);
    }
    cout<< maxLength;

    
}