(C언어) 백준 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<stdio.h>
#include<stdlib.h>


int main(void)
{
    int N = 0,min,max=0;

    scanf("%d",&N);

    int* arr = (int*)malloc(sizeof(int)*N);
    int* DP = (int*)malloc(sizeof(int)*N);

    for(int i=0;i<N;i++)
    {

        scanf("%d",&arr[i]);
        
        min = 0;
        DP[i] = 1;

        for(int j=0;j<i;j++)
        {
            if(arr[i]>arr[j] && min < DP[j])
            {
                min = DP[j];
            }
        }

        DP[i] = min + 1;
        if(max < DP[i])
        {
            max = DP[i];
        }
    }

    printf("%d",max);
}

 

 

 

 

요번 DP문제는 말로 하기 힘든데,

먼저 입력 받은 값을 arr배열에 저장합니다.

그 다음에 정수형 min의 값을 0으로 지정하고 해당 인덱스의 DP 배열의 값을 1로 저장합니다

arr배열은 입력받은 값을 저장한 배열로 입력받은 값과 전에 저장되어 있는 배열의 값과 비교를하여 작을 경우 해당 인덱스의 DP의 값을 min으로 저장합니다.

이중 반복문이 끝난 후에 해당 DP의 값을 min + 1로 저장합니다. 

마지막 0으로 저장한 max와 비교하여 max값을 설정해줍니다.

 

말로 하면 전혀 무슨말인지 모를거에요 ...ㅠㅠ 간단히 말해서 입력받은 값과 전에 비교받은 값과 비교를 하여 동시에 해당 인덱스의 DP의 값과 비교를 하는건데 여기서 DP의 값들은 다 길이의 값입니다.

 

디버깅을 하면서 차근차근 하시면 분명히 이해하실겁니다...!