11053 LIS(Longest Increasing Subsequence)

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

11053번: 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

40582

15259

10349

37.190%

문제

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

예제 입력 1 복사

6 10 20 10 30 20 50

예제 출력 1 복사

4

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: harinboy

<개인풀이>

<순서>

1.

최고 증가 부분 길이를 나타내는 수열의 마지막 수 A[i]

{ A[0], A[1], A[2], ...... ,A[k], A[i] }

  -> for( i =0 ; i <= 입력받을수 ; ++i)

       for( k=0; k<i ; ++k)

        -> 현재 인덱스 i 의 A[i] 값과, 현재 인덱스의 전까지 수들을 비교하여 작은 값을 찾고,

            해당 가중치( k) 의 +1을 한 수가 현재 인덱스의 가중치 값이나온다. 

2. 

길이의 가중치를 저장한 dp값

dp[i] = dp[k] +1 의 값,   // (dp[k] + 1)은 dp[i]를 만드는 최장길이가 되기 바로 이전의 값에 +1의 가중치를더하여 

                                // dp[i]를 만듦.

 

3.

이중포문을 활용하여 현재 인덱스 값 a[i]와 a[i] 전 수들까지 작은수를 찾고,

작은수의 인덱스(before) 의 길이에 +1을 한 값과 비교하여 마지막 수 까지 길이를 저장.

 

4.

max값 LIS 찾기

 

#include<stdio.h>
 
int n[1001];
int a[1001];
 
int main(void)
{
    int get_count = 0;
 
    scanf("%d", &get_count);
 
    for (unsigned short i = 0; i < get_count; ++i)
        scanf("%d", &n[i]);
 
    a[0] = 1;
    for (unsigned short i = 1; i <= get_count; ++i)
    {
        a[i] = 1;
        for (unsigned short before = 0; before < i; ++before)
        {
            if (n[before] < n[i] && a[before]+1>a[i])
            {
                a[i] = a[before] + 1;
            }
        }
    }
    int max=a[0];
    for (unsigned short i = 0; a[i] != 0; i++)
    {
        if (max < a[i])
            max = a[i];
    }
 
    printf("%d\n", max);
    return 0;
}