[백준/C++] 11053번 가장 긴 증가하는 부분 수열

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

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

문제 분석

코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m;
int dp[1001],arr[1001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    //memset(dp, 1, sizeof(dp));

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

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

 

문제풀이

이 문제는 수열안에서, 증가하는 부분 수열 중 가장 긴 수열을 찾는 문제이다.

1. 부분 수열의 길이를 나타낼 dp table을 하나 생성한다.

2. 첫번째 for문을 돌면서 dp table을 1로 초기화한다.(자기 자신의 길이는 1이므로)

3. 수열의 첫번째 인덱스부터 i번째까지 돌면서 (두번째 for문)

i번째 숫자가 j번째 숫자보다 크다면(=해당 인덱스의 수보다 앞에 위치한 수들을 검사했을 때 자신보다 작다면) dp[i] = max(dp[i],dp[j]+1)이라는 점화식을 이용해 해당 인덱스에서의 증가하는 부분 수열의 길이를 구한다.

예를 들어, 입력이 10 20 10 30 20 50이라면 dp[0]=1이 되고, dp[1]은 max(1, 1+1)을 통해 2가 되고,

dp[2]는 자신보다 작은 수가 없으므로 1, dp[3]은 max(1,2+1)을 통해 3이된다...

4. 두번째 for문이 끝나면, 현재 sum값과 새로 구해진 dp[i]값중 큰 값(= 가장 긴 길이)를 sum에 저장한다. 즉, dp[0]부터 dp[n-1]까지에서 제일 큰 값이 정답이 된다.

​