Softeer [level 3] 징검다리 (C 언어)

https://softeer.ai/practice/info.do?idx=1&eid=390&sw_prbl_sbms_sn=171891 

Softeer

Code:

#include <stdio.h>
 
int main()
{
    int n;
    int arr[3001] = { 0, };
    int dp[3001] = { 0, };
    int max=0;
    int value_m = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dp[0] = 1;
    for (int i = 1; i < n; i++)
    {
        max = 0;
        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                if (max < dp[j])
                {
                    max = dp[j];
                }
            }
        }
        dp[i] = max+1;
    }
    for (int i = 0; i < n; i++)
    {
        if (value_m < dp[i])
        {
            value_m = dp[i];
        }
    }
    printf("%d", value_m);
}

문제풀이:

가장 증가가 긴 부분을 뽑아내면 쉽게 풀리는 문제이다.