backjoon - 11053 번 [ 가장 긴 증가하는 부분 수열 ]

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

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

 

 

문제는 다음과 같다.

 

 

 

 

 

 

한 줄의 수열이 주어 지면, 가장 길게 증가하는 수열의 길이를 구해야 된다. 위와 같은 문제를 해결하기 위해 접근해야 하는 방식은 다음과 같다. 우선 수열 [10, 20, 10 ,30 ,20 ,50]에서 어떤 i 번째 의 가장 긴 수열을 구하기 위해서는 현재 i보다 작은 i-1, i-2,,, i-N ( i-N이 0일 때까지 ) 번째 인덱스의 값들 중 i번째 index의 값보다 작으면서 그중에서 가장 큰 값을 찾아 그 가장 큰 값의 인덱스 번째의 수열 길이  +1을 하면 현재 i번째 인덱스의 값의 수열의 길이를 구 할 수 있다. 예를 들어 위 예제에서 2번째 인덱스( 20 )까지의 가장 긴 수열을 구하기 위해서는 1번째 인덱스의 값이 10이므로 20보다 작으니깐 증가하는 수열의 조건이 충족된다. 그러므로 1번째 인덱스의 가장 긴 부분 수열 값인 1 ( 첫 번째 인덱스의 수열 길이는 1이니깐 ) +1을 한 값인 2가 2번째 인덱스까지의 가장 긴 수열 길이가 된다. 

 

 

예시를 몇 개 더 들어서 3번째 인덱스까지의 수열의 길이를 구해보면, 3번째 인덱스의 값인 10 보다 이전 인덱스의 값들인 10, 20을 비교해보면 3번째 인덱스 10보다 작은 값들은 없다. 그러므로 3번째 인덱스까지의 수열 길이는 1이 된다. 다음으로 4번째 인덱스까지의 수열 길이를 구해보면 4번째 인덱스의 값인 30과 이전 인덱스들의 값인 10, 20, 10을 비교해보면 충분히 증가하는 긴 수열의 조건이 충족된다. 그리고 그중에서 이전 인덱스 들의 수열 길이중 가장 길게 만들어진 2번째 인덱스까지의 길이 2 + 1을 한 값이 4번째 인덱스까지의 수열의 길이가 된다.

 

 

4번째 인덱스까지의 수열의 길이를 표로 나타내 자면 다음과 같다.

 

인덱스 번호	1	2	3	4
인덱스의 값	10	20	10	30
인덱스의 증가 수열	1 ( 제일 처음 이니깐 )	2	1	3

 

 

즉 현재 인덱스의 가장 긴 증가수열을 구하기 위해서는 다음과 같은 식을 적용하면 된다.

현재 index증가 수열 = 이전 index들의 증가수열 중 가장 큰 값 + 1

 

 

이제 코드를 작성하기 위한 방법은 다음과 같다. 우선 index들의 값이 들어가는 배열 하나( 이 배열의 이름을 arr이라고 가정 )와 각 인덱스들의 가장 증가하는 수열의 길이를 넣기 위한 배열( 이 배열의 이름을 dp라 가정 )을 만든다. 이후 dp배열의 젤 첫 번째 인덱스에다가 1을 넣어준다. 왜냐하면 아까도 설명했듯이 첫 번째 인덱스의 증가수열은 1이기 때문이다. 이후 반복문을 통해 각 인덱스의 값들에 접근하면서 반복문 내부에서 또 한 번 반복문을 돌려 현재 i 번째 인덱스의 값과 이전 i-1 , i-2... 번째 인덱스의 값들과 비교를 해서 현재 인덱스보다 이전 인덱스들의 값이 작고, 그중에서 가장 긴 증가수열을 찾아 위 식처럼 이전 index들의 증가 수열중 가장 큰 값 + 1을 하여 구할 수 있다.

 

 

내가 작성한 코드는 다음과 같다.

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
    
    int arr[1000]={0,};
    int dp[1000]={0,};
    int N=0;
    int max_data=0;
    
    
    cin >> N;
    
    for(int i=0;i<N;i++){
        cin >> arr[i];
    }
    
    dp[0] = 1;
    
    for(int i=1;i<N;i++){
        max_data=0;
        for(int j=0;j<i;j++){
            if(arr[j]<arr[i] && max_data<dp[j]){
                max_data=dp[j];
            }
        }
        if(max_data==0){
            dp[i]=1;
        }
        else{
            dp[i]=max_data+1;
        }
    }
    
    cout << *max_element(dp,dp+N) << endl;
    
    
    return 0;
}

 

 

위와 같이 만약 현재 인덱스의 값보다 이전 인덱스들의 값들 중 작은 게 없으면 그냥 현재 인덱스의 수열 길이 배열 에대가 1을 넣어 주었다.

이후 구한 수열들중 *max_element() 함수를 사용해 가장 긴 수열을 구하였다.