백준 11053 C++ 가장 긴 증가하는 부분수열

LIS (Longest Increasing Subsequence) 기초 문제이다.

이 문제를 응용해서 낼 수 있는 문제가 많으므로 반드시 알고리즘을 알아두어야 한다.

 

시간 제한	메모리 제한	정답률
1초	256MB	36.752%

 

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

핵심

• dp[k] : k번째 항이 마지막 수일때, 증가하는 부분수열 길이 중 최댓값
• dp[마지막수]가 반드시 최댓값이 되는 건 아니다.

코드

#include <iostream>
#include <algorithm>


using namespace std;

int n;
int dp[1010];
int arr[1010];
int answer;


int main(int argc, char* argv[]) {
	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    
    dp[1] = 1;
    
    int maxx = 1;
    for(int i=2;i<=n;i++){
        maxx = 1;
        
        for(int j=1;j<i;j++){
            if(arr[j] < arr[i]){
                if(dp[j] + 1 > maxx){
                    maxx = dp[j] + 1;
                }
            }
        }
        
        dp[i] = maxx;
    }
    
    //꼭 마지막 수에서 끝나야 최댓값인건 아니므로, 전수조사해야함.
    for(int i=1;i<=n;i++){
        if(dp[i] > answer) answer = dp[i];
    }
    
    cout << answer << '\n';
    
	
	return 0;
}

해설

10 20 30 19 50 40 15

이렇게 수열이 있다고 하자.

40으로 끝나는 증가하는 수열 중 가장 긴 것의 길이를 구하는 상황을 생각하자.

우선, 40 앞에 있는 녀석들 중 40보다 작은 것을 찾아보자.(50빼고 다 일 것이다)

 

10에서 바로 40으로 간다면 dp[6] = dp[1] + 1 이 될 것이다.

20에서 바로 40으로 간다면 dp[6] = dp[2] + 1 이 될 것이다.

30에서 바로 40으로 간다면 dp[6] = dp[3] + 1 이 될 것이다.

19에서 바로 40으로 간다면 dp[6] = dp[4] + 1 이 될 것이다.

50은 40보다 크므로 50에서 40으로 갈 수 없다.

 

구한 값 4개 중 가장 큰 값이 dp[6]으로 들어가면 된다.

이런식으로 dp[n]까지 구하면 된다.

 

여기서 조심할 점은 무조건 dp[n]이 모든 dp값 중 최댓값이 아니라는 것이다.

위 경우가 그 예시인데 dp[7] = 2 밖에 되지 않는다. (10, 15)

그러므로 구한 dp값들 중 최댓값을 구하는 작업을 더 해야한다.