[Baekjoon] 가장 긴 증가하는 부분 수열 4

👀 문제 설명

문제

수열 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

6

10 20 10 30 20 50

 

예제 출력 1

4

10 20 30 50

 

✍🏻풀이

이전에 푼 [Baekjoon] 가장 긴 증가하는 부분 수열과 같은 문제인데, 차이점은 LIS의 원소들을 출력하는 것이다.

LIS의 길이를 구하는 방법은 이전에 풀었을 때와 같다.

 

LIS의 원소들을 구하는 방법은 다음과 같이 해결했다.

 

변수 leng에 LIS의 길이(ans)를 담고, for문을 통해 dp 배열을 뒤에서부터 접근한다.

dp 배열에서 dp[i]가 leng과 같은 경우, a[i]는 LIS의 원소에 속한다는 뜻이므로, lis벡터에 a[i]를 넣어준다.

 

for문을 빠져나오면, lis벡터에는 원소들이 거꾸로 담겨있다. (dp 배열을 뒤에서부터 접근했으므로)

algorithm 헤더의 reverse 함수를 사용하여 lis 벡터를 뒤집어주면 끝!

 

이 과정에서 나는 inDp라는 변수를 사용해서 다음과 같이 a[i]의 원소들이 증가하는 원소인지 판단해주려 했다.

// leng을 1씩 줄여나가면서,,
    int leng = ans;
    int inDp = 100;
    for (int i = N - 1; i >= 0; i--) {
        if (dp[i] == leng) {
            if (a[i] < inDp) {
                inDp = a[i];
                v.push_back(inDp);
                leng--;
            }
        }
    }

여러 테스트 케이스를 넣어봐도 맞는 답이 나오는데, 문제에선 자꾸 틀렸다고 나와서,,ㅠ

inDp를 사용하지 않고, a[i] < inDp인지 확인하는 if문도 삭제한 후, 다음과 같이 풀었더니

// 변수 leng에 ans 값을 담고, for문을 통해 dp 배열에 접근한다.
    // dp 배열에서 dp[i]가 leng과 같은 경우, a[i]는 LIS의 원소에 속한다는 뜻이므로,
    // lis 벡터에 넣어준다.
    int leng = ans;
    
    for (int i = N - 1; i >= 0; i--) {
        if (dp[i] == leng) {
            lis.push_back(a[i]);
            leng--;
        }
    }

 

드디어 정답 ㅠ 

드디어 맞았다고 나왔다.. (그런데 아무리 생각해도 이전 답이 왜 틀린건지 아직도 모르겠다..)

=> 추가) 그냥 내가 바보였음..^^!

inDp를 애초에 100으로 초기화해서 틀린거였다..!ㅎㅎ;; 원소가 최대 1000인데, 초기화를 100으로 해서 ,,^^ 틀린거였다,,^^!

 

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int a[1001];
int dp[1001];
vector<int> lis; // 가장 긴 증가하는 부분 수열

int main() {
    cin >> N;
    
    fill_n(dp, 1001, 1); // dp 배열을 1로 초기화
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    int ans = 1; // 가장 긴 증가하는 부분 수열의 길이
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) { // a[j]가 a[i]보다 작으면 i를 포함한 증가하는 부분 수열이 될 수 있다.
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        
        ans = max(ans, dp[i]);
    }
    
    // 변수 leng에 ans 값을 담고, for문을 통해 dp 배열에 접근한다.
    // dp 배열에서 dp[i]가 leng과 같은 경우, a[i]는 LIS의 원소에 속한다는 뜻이므로,
    // lis 벡터에 넣어준다.
    int leng = ans;
    
    for (int i = N - 1; i >= 0; i--) {
        if (dp[i] == leng) {
            lis.push_back(a[i]);
            leng--;
        }
    }
    
    reverse(lis.begin(), lis.end()); // dp 배열을 뒤에서부터 접근했으므로, lis 벡터를 reverse 시켜준다.
    
    cout << ans << endl;
    
    for(int i = 0; i < lis.size(); i++) {
        cout << lis.at(i) << " ";
    }
    
    return 0;
}