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

코드

#include <iostream>

using namespace std;

/* 조건 */
#define MAX_N 1001
#define MAX_A 1001

/* 변수 */
int N, arr[MAX_N], dp[MAX_N];
int result = 1; // 최댓값

int main() {
    cin >> N;

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

    for(int i = 0; i < MAX_N; i++)
        dp[i] = 1;

    for (int i = 0; i < N; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[j] < arr[i] && dp[j]+1 > dp[i]) {
                dp[i] = dp[j] + 1;
                if(result < dp[i]) {
                    result = dp[i];
                }
            }
        }
    }

    cout << result << '\n';

    return 0;
}

풀이

코드 설명

main 함수

• N을 입력 받고 N만큼 arr에 값을 입력받는다.
• 부분수열의 길이를 저장하는 dp를 모두 1로 초기화한다.
  • 자신을 포함할 경우 1이기 때문에 1로 초기화
  • arr[i] 이전에 자신보다 작은 숫자가 없으면 값을 계산하지 않기 때문에 미리 초기화 해주었다.
• 0부터 N까지의 각 i에 대하여, 0부터 i까지의 j에 대해 arr[j]들 중 arr[i]보다 작은 arr[j]가 있으면 dp[i] = dp[j] + 1
  • 0부터 N까지 차근차근 i앞의 가장 긴 증가하는 부분수열에 arr[i]를 다음 숫자로 포함할 수 있는지 확인하는 방식
  • 모든 i에 대해 위의 과정을 반복하다보면 dp배열에는 각 숫자에 대해 자신이 포함되는 부분 수열 중 가장 긴 길이의 값이 저장되어 있다.
  • 위의 과정을 반복하는 중 result의 값과 dp[i]의 값을 비교하면서 최댓값을 찾아낸다.
• 최댓값을 찾아낸 result출력

출처

백준 [11053] 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053