[백준 BOJ 11053번] 가장 긴 증가하는 부분 수열(C / C++ ) [다이나믹프로그래밍, DP]

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256MB	71427	27463	18124	36.848%

 

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입력

6
10 20 10 30 20 50

 

예제 출력

4

 

풀이

O(n^2)의 시간복잡도를 보이고 있어 배열에 수열값이 입력되는대로 그때그때 탐색을 하는 방법을 선택했습니다.

배열에 값이 입력되면 임시 max값을 0으로 초기화 하여 이전에 입력했던 수열값과 수열의 길이(dp배열)를 비교하며 진행합니다.

만약 현재 입력된 값이 이전에 입력된 수열값보다 크고 그 이전에 입력된 수열의 수열 길이가 임시 max값보다 크면 max값을 갱신합니다.

max값 갱신이 끝나면 현재 입력된 수열 인덱스의 수열길이 배열에 max+1을 저장한 후 res값 보다 크면 res값을 갱신하여 문제를 해결합니다.

기존 dp문제는 dp배열의 마지막 인덱스를 출력하는 방식으로 출력을 하였지만, 마지막 인덱스 수열 길이가 가장 길다고 장담할 수 없으므로 res값에 저장된 최고 길이를 출력하여야 합니다.

 

코드

// 가장 긴 증가하는 부분 수열
// dp
#include<iostream>
using namespace std;
int dp[1001]={0,1};
int arr[1001];
int main(){
    int N,res=0;
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>arr[i];
        int max=0;
        for(int j=1;j<=i;j++)
            if(arr[i]>arr[j]&&dp[j]>max)max=dp[j];
        if((dp[i]=++max)>res)res=dp[i];
    }
    cout<<res;
}

 

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

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