[C] 백준 11722번 가장 긴 감소하는 부분 수열

링크
https://www.acmicpc.net/problem/11722

문제

---

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력

---

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 A$_i$가 주어진다. (1 ≤ A$_i$ ≤ 1,000)

출력

---

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1

---

6
10 30 10 20 20 10

예제 출력 1

---

3

아이디어 스케치

---

예제에서 주어진 수열 A를 바탕으로 가장 긴 감소하는 부분 수열의 길이를 구해보면

A = {10, 30, 10, 20, 20, 10}

먼저 각 인덱스의 숫자를 선택했을 때 나올 수 있는 부분 수열의 길이는 1이다.
따라서 인덱스별로 수열의 길이를 1로 초기화한다.

dp[i]는 i번째 까지의 부분 수열의 최대 길이

Index[0] 을 선택했을 때,
조건을 만족하는 부분 수열은 {10} 이고, 길이는 1이다.
이때 dp[0] = 1

Index[1] 을 선택했을 때,
조건을 만족하는 부분 수열은 {30} 이고, 길이는 1이다.
이때 dp[1] = 1

Index[2] 를 선택했을 때,
조건을 만족하는 부분 수열은 {30, 10} 이고, 길이는 2이다.
이때 dp[2] = 2

Index[3] 을 선택했을 때,
조건을 만족하는 부분 수열은 {30, 20} 이고, 길이는 2이다.
이때 dp[3] = 2

Index[4] 를 선택했을 때,
조건을 만족하는 부분 수열은 {30, 20} 이고, 길이는 2이다.
이때 dp[4] = 2

Index[5] 를 선택했을 때,
조건을 만족하는 부분 수열은 {30, 20, 10} 이고, 길이는 3이다.
이때 dp[5] = 3

위 과정에서 dp[i]가 갱신되는 경우를 살펴보면,

현재 인덱스 i의 값을 선택했을 때, 현재 구한 부분 수열의 최대길이보다 1칸 만큼 더 길어지는 경우에 dp[i]의 값이 갱신되는 것을 알 수 있다.

즉, dp[i] 의 값보다 dp[j] (이때 j는 i보다 작은 인덱스)에 1을 더한 값이 더 큰 경우에 dp[i]를 dp[j]+1로 갱신한다.

전체 코드

---

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int N;
    int* dp;
    int* arr;
    int i, j;
    int max = 0;

    scanf("%d", &N);    // 수열의 크기를 입력 받음

    // 동적 할당
    dp = (int*)calloc(N, sizeof(int));
    arr = (int*)calloc(N, sizeof(int));

    for (i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    for (i = 0; i < N; i++) {
        dp[i] = 1;  // 초기값을 1로 설정
        for (j = 0; j < i; j++) {
            if (arr[i] < arr[j] && dp[i] < dp[j] + 1)   // 현재 선택한 값이 인덱스 j에 해당하는 값보다 작고, j까지 구한 부분 수열의 최대 길이+1보다 dp[i]가 작은 경우
                dp[i] = dp[j] + 1;      // 값을 갱신
        }
    }

    for (i = 0; i < N; i++) {
        if (max < dp[i])
            max = dp[i];        // 구한 부분 수열의 길이 중 가장 큰 값을 구함
    }

    printf("%d", max);          // 결과 출력

    // 메모리 해제
    free(arr);
    free(dp);

    return 0;
}

제출 결과

---