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

 

 

 

 

 

 

 

해당 문제는 백준 사이트에서 풀 수 있습니다.

 

www.acmicpc.net/problem/11053

 

 

1. 문제

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

 

예제 입력 1                      예제 출력 1

6                                                4

10 20 10 30 20 50

 

2. 조건

여기서 말하는 가장긴 수열은 다음과 같다.

 

1. 연속적으로 증가하는 수열 중 가장 긴 수열.

위 예제에선 10, 20, 30, 50 순으로 증가하는 수열이 가장 긴 수열임으로 4를 출력한다.

 

다른 예제를 살펴보자.

ex) 30 10 30 70 20 50

가 있을 때 가장 긴 수열은 10, 20, 50 이다. 즉 3을 출력하면 된다.

 

이정도 예제면 충분이 이해가 되실꺼라 믿습니다.

 

3. 풀이

해당 문제는 dp를 이용해 풀어야 합니다.

 

2중 for문으로 풀면 코드가 너무 복잡해 지고 구현도 어렵습니다.

 

해당 dp 풀이 방법은 현재 내가 있는 지점까지 검사하되, 연속되는 수열이 최소 몇개인지 

비교하면서 구하면 됩니다.

(이렇게 말해놓고 저도 무슨말인지 못알아 먹겠네요....)

 

그림을 통해 보시죠.

즉, 자신보다 작은 숫자의 위치를 기준으로 해당 dp중 가장 큰 값으로 갱신하면서 이동해주면 됩니다.

여기서 dp갱신 조건은 자신보다 작으면서 dp가 내가 갖고있는 값보다 크면 갱신해주는 것입니다.

 

이것이 가능한 이유는 자신보다 작은 값 중 dp에 있는 값은 결국,

자신보다 작은 연속된 순열의 갯수를 의미하기 때문에 이런식으로 가능한 것입니다.

 

이해가 안되면 코드를 보고 일일히 A4용지에 써가며 해보시면 될 것입니다.

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>

#pragma warning(disable: 4996)

using namespace std;

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    int answer = 0;
    
    int dp[1001];
    vector<int> v;
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> K;
        v.emplace_back(K);
        int dp_max = 0;

        for (int j = 0; j < v.size(); j++) {
            if (v[i] > v[j]) {
                if (dp_max < dp[j])
                    dp_max = dp[j];
            }
        }
        dp[i] = dp_max + 1;
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;

    return 0;
}