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

1.문제

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

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

 

2. 풀이

가장 긴 증가하는 부분수열은 LIS(Longest Increasing Sequence)로 매우 유명한 알고리즘이다.
DP를 이용하는 문제는 매번 어렵다.

 

문제에는 두가지 배열이 있다.

1.  숫자들의 나열이 담긴 배열
2. 현재 인덱스에 해당하는 숫자까지의 LIS를 저장하는 배열

문제에서 2)의 배열에서 이전까지의 LIS 값을 얻어 최종적인 LIS 값을 얻어 낼 수 있으므로
DP를 이용해서 채우고 결과를 얻는 배열이다.

 

2)의 DP 배열을 채우는 과정에서 2개의 for문이 사용된다.

1. 바깥의 for문
   바깥의 for문에서는 숫자들의 나열이 담긴 배열(1)에서 인덱스를 하나하나 증가시킨다.
   이를 통해 배열 중 숫자를 하나 지정해 아래의 for문에서 사용한다.
   지정한 배열의 숫자를 지정된 숫자라고 하자.안의 for문
2. 안의 for문에서는 지정된 숫자를 포함하는 LIS 길이를 구한다.
   for문에서 숫자들의 나열이 담긴 배열(1)에서 맨 처음 숫자부터 지정된 숫자 전까지 접근한다.
   접근한 원소가 지정된 숫자보다 작은 경우
   - 접근한 원소를 포함하는 LIS에 지정된 숫자를 포함해 새로운 LIS를 만들 수 있으므로
   - 지정된 숫자 이전의 LIS 중 가장 큰 것을 구하고 거기에 +1하면
   - 지정된 숫자를 포함한 LIS의 길이를 구할 수 있다.
3. 다시 바깥의 for문
   2)의 과정을 통해 구한
   지정된 숫자를 포함한 LIS 길이와 지정된 숫자 이전까지의 LIS(현재 원소를 포함하지 않은 LIS) 길이를 비교해
   지정된 원소까지의 LIS 길이를 갱신한다.
4. 중첩된 2개의 for문을 거치면 최종적으로 전체 숫자 나열의 LIS를 구할 수 있다.

 

 

이미지로 설명하면 아래와 같다.

 

 

 

3. 코드

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int arr[1001];
    int dp[1001] = { 0 }; // dp를 수행할 배열
    // 숫자 배열 입력
    for (int i = 0; i < n; i++) 
        cin >> arr[i];
 
    int max = 0; // 최종 LIS 길이
    for (int i = 0; i < n; i++) {
        int maxDP = 0; // 현재 숫자를 포함한 LIS
        for (int j = 0; j < i; j++) { 
            if (arr[j] < arr[i]) { // 증가하는 부분 수열이 가능 한 경우
                if (maxDP < dp[j]) 
                    maxDP = dp[j]; // 현재 숫자를 포함한 LIS 갱신
            }
        }
        dp[i] = maxDP + 1; // 현재 숫자를 포함해야 하므로 + 1
        if (max < dp[i]) max = dp[i]; // 최종 LIS 갱신 
    }
 
    // 결과 출력
    cout << max <<'\n';
}