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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

가장 긴 증가하는 부분 수열

문제

문제

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

 

풀이

수열 A가 주어졌을 때 수가 증가하는 부분 수열 중 가장 긴 수열을 찾는 문제다.

이 부분 수열을 어떻게 구할까.

 

조금 바꿔서 생각하자.

 

아래의 A 수열로 알아보자. i번째까지의 수들로 구성된 증가하는 부분 수열을 찾는다. 그리고, 증가하는 부분 수열에는 항상 i번째 자기 자신이 들어가야한다고 생각해보자.

 

A = [ 10, 20, 11, 13, 22, 30 ]

 

 

첫 번째 수 까지의 증가하는 부분 수열은,

A[1] = [ 10 ] 으로 길이는 1이다.

 

두 번째 수 까지의 증가하는 부분 수열은,

A[2] = [ 10, 20 ] 으로 길이는 2이다.

 

세 번째 수 까지의 증가하는 부분 수열은,

A[3] = [ 10, 11 ]로 길이는 역시 2이다.

 

네 번째 수 까지의 증가하는 부분 수열은,

A[4] = [ 10, 11, 13 ] 으로 길이는 3이다.

 

 

여기 까지의 과정만을 보고 규칙을 발견해보자.

 

일단, 자기 자신을 포함하는 경우가 있기 때문에 증가하는 부분 수열의 최소 길이는 무조건 1이 된다.

그래서, 길이를 저장할 배열을 하나 만들어서 그곳에 저장시켜보자.

 

dp[i] = i번째 수를 포함하는 증가하는 부분 수열의 길이

 

첫 번째 수 까지의 증가하는 부분 수열은 항상 1이다.

dp[1] = 1

 

두 번째 수 까지의 증가하는 부분 수열을 보자.

이전까지의 부분 수열의 길이(dp[1])는 1이다.

여기서, 자기 자신인 20은 10보다 크기 때문에 증가하는 부분 수열에 포함해준다.

A[2] = [ 10, 20 ]로 만들어 길이 2로 더 길어졌다.

 

그래서, dp[1] 까지의 거리에서 자기를 추가한 길이인 2를 저장한다.

dp[2] = dp[1] + 1 = 2

 

세 번째 수 까지의 증가하는 부분 수열을 보자.

첫 번째 수인 10은 자신의 수인 11보다 작다. 그래서 첫 번째 수 뒤로 자신을 포함해 증가하는 부분 수열을 만들 수 있다.

그런데, 두 번째 수인 20보다는 작다. 그래서 두 번째 수 뒤에 붙어서 증가하는 부분 수열을 만들 수가 없다.

 

따라서, dp[3]의 값은 dp[1] + 1인 2가 된다.

 

네 번째 수 까지의 증가하는 부분 수열을 보자.

13 본인은 각각 10과 11보다는 크고, 20보다는 작다. 이 말은 13은 dp[1] 뒤에 붙을 수도 있고 dp[3] 뒤에 붙을 수도 있다는 소리가 된다. 문제는 가장 긴 증가하는 부분 수열을 찾는 것이기 때문에 dp[3]뒤에 붙어야 길이가 더 길어진다.

 

그래서, dp[4]의 값은 dp[3] + 1인 3이 된다.

 

즉 i번째의 수는 이전에 나온 수들과 비교해서 더 작으면, 그 수의 뒤에 붙어 증가하는 부분 수열을 이어나간다.

 

dp[i] = dp[j] + 1

 

문제는 가장 긴 증가하는 부분 수열을 찾는 것이라고 했으니, 그 중에서 가장 긴 길이를 찾아야한다. 그래서 아래 점화식을 완성할 수 있다.

 

if A[j] < A[i] : DP[i] = max(DP[j] + 1, DP[i])

 

#include <iostream>

using namespace std;

int dp[1001];
int arr[1001];

int main() {
    int N;
    cin >> N;
    int answer = 0;

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

    for (int i = 1; i <= N; i++) {
        dp[i] = 1;

        for (int j = 1; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;
    
    return 0;
}