[BOJ 백준] 11053번 : 가장 긴 증가하는 부분 수열 (C++)

[BOJ 백준] 11053번 : 가장 긴 증가하는 부분 수열 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 수열 최대 크기가 1'000이므로 2중 for문을 통해서 완전탐색을 해도 해결 가능

2. Top-Down 방식의 DP를 통해서 해결 가능

2-1. 마지막에 있는 수부터 검사

2-2. 검사하는 수의 바로 앞부터 수열의 가장 앞까지 작은 수가 발견될 때마다 재귀

2-3. 이미 검사를 한 수는 바로 반환

2-4. 검사를 하지 않은 수는 2-2 과정을 진행

2-5. 검사를 모두 진행했을 때, 해당 위치에서 가장 긴 증가하는 부분 수열의 횟수를 저장 후, 반환

 

과정

 

위 문제는 입력 크기가 작아 2중 for문을 통한 완전탐색으로도 해결할 수 있습니다.

 

하지만, Top-Down 방식의 DP를 통해서 예제 1번을 자세히 확인하겠습니다.

 

먼저, 초기 상태입니다.

 

뒤에서부터 검사를 진행하니, 마지막 요소인 5부터 검사를 진행합니다.

index가 5인 요소에는 방문한 적이 없으니(0의 값을 가지고 있음) 검사를 계속합니다.

가장 긴 증가하는 부분 수열에서는 본인도 하나의 증가하는 수로 보므로 1로 초기화를 하고 검사를 해야 합니다.

그렇기에, 해당 요소의 값이 0이면, 아직 검사하지 않았다고 처리할 수 있습니다.

 

바로 앞에 있는 요소 4의 값은 20입니다. 이는 50보다 작으므로, 재귀 함수를 통해 진입합니다.

요소 4는 계산한 적이 없으므로, 다시 요소 4에 대한 검사를 진행합니다.

 

요소 3의 값(30)은 요소 4의 값(20)보다 크므로, 검사하지 않습니다.

그 앞에 있는 요소 2(10)에 대해서 검사를 진행합니다.

 

요소 2에서는 앞에 더 이상 작은 수가 없으므로 자기 자신의 횟수 값인 1을 반환합니다.

반환된 값에서 자기 자신까지 포함하므로 요소 4의 횟수는 2가 됩니다.

 

요소 4에서는 요소 2까지 검사를 했습니다. 그래서, 앞에 있는 요소 1과 요소 0에 대해서 검사를 진행합니다.

하지만, 요소 1(20)은 요소 4(20)와 같은 값을 가지므로, 더 작은 값인 요소 0(10)에 대해서만 재귀 함수를 호출합니다.

 

요소 0(10)을 기준으로 더 이상 앞에 검사할 수 있는 요소가 없습니다.

그래서, 바로 요소 0의 횟수인 1을 반환합니다.

 

요소 0에서의 반환값(1)과 자기 자신을 더하면, 2입니다.

이는 기존과 동일한 값이므로 변동되지 않습니다.

 

요소 4에 대한 검사가 끝났으므로, 다시 요소 4에 대한 횟수(2)를 반환합니다.

 

요소 4의 반환값(2)에서 자기 자신을 더한 값은 3입니다.

이는 기존 1보다 크므로, 3으로 교체합니다.

요소 5(50)에서 요소 4에 대한 검사가 완료되었으므로, 요소 3(30)에 대한 검사를 진행합니다.

 

요소 3은 아직 검사를 하지 않았으므로, 자기 자신인 1의 값을 대입합니다.

 

그리고, 요소 3을 기준으로 앞의 수에 대해서 검사를 진행합니다.

 

요소 2의 횟수(1)는 0이 아닙니다.

따라서, 바로 1을 반환하고, 자기 자신인 1을 추가해서 최댓값을 비교합니다.

 

다음으로 요소 1에 대해서 검사를 진행합니다.

요소 1(20)은 요소 0(10)보다 큽니다.

따라서, 요소 0에 대한 검사를 진행하지만, 요소 0은 이미 검사했으므로 횟수인 1을 바로 반환합니다.

 

 

요소 1에 대한 검사도 완료되었으므로 그 횟수인 2를 반환합니다.

요소 1의 횟수(2)와 요소 3 자기 자신을 더해서 3이 됩니다.

이는 기존 2보다 크므로 3으로 교체합니다.

 

요소 3에 대한 검사도 완료했으므로, 횟수인 3을 반환합니다.

요소 5에 대한 검사가 완료되었습니다.

따라서, 이에 대한 최댓값은 4입니다.

 

 

주의점

 

위 예제는 마지막 요소가 수열 중에서 가장 큰 값을 가지고 있기에 가능합니다.

만약에, 아래처럼 입력이 되는 경우, 오류가 발생할 수 있습니다.

4
10 20 50 10
// answer : 3

 

그러므로, 마지막 요소가 아니라 각 요소별 검사도 진행해야 합니다. 

 

---

03. 정답 코드

// 실버 2 - 11053번 : 가장 긴 증가하는 부분 수열
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

vector<int> g_nums;
vector<int> g_dp;

void inputInfo(const int N)
{
    g_nums = vector<int>(N);
    g_dp = vector<int>(N, 0);

    for(int& each : g_nums)
        cin >> each;
}

int search(const int idx)
{
    int& ref = g_dp[idx];

    // 이미 계산한 경우가 있을 때, 미리 반환
    if(ref != 0)
        return ref;
        
    // 자기 자신도 포함
    ref = 1;

    // 자기보다 작은 값과 비교
    for(int i = idx-1; i >= 0; i--)
    {
        // 값이 작아질수록 + 1
        if(g_nums[idx] > g_nums[i])
            ref = max(ref, search(i) + 1);
    }

    return ref;
}

// 시작점을 뒤에서부터 하나씩 다 돌기
int simulate(const int N)
{
    int result = 0;

    // 시작점
    for(int i = N-1; i >= 0; i--)
        result = max(result, search(i));

    return result;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 수열 A 크기 N
    int N;
    cin >> N;

    inputInfo(N);
    cout << simulate(N) << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!