오늘부터 동기들과 함께 1일 1ps를 시작했다. 19학점의 수업, 칵테일 동아리, 연애... (학동연) 등 여러 가지와 병행하기가 쉽지는 않겠지만 이왕 시작한 거 최대한 해보려고 노력할 것이다.

acmicpc.net/problem/11053
참고로 이 문제는 Longest Increasing Sequence(LIS)라고도 불리는 제법 유명한 알고리즘이다.

DP를 이용해서 푸는 문제이다.
dp[i]-> A[i]를 가장 마지막 원소로 가지는 LIS

예를 들어 백준에 예시로 나와 있는 input에 대해 DP 테이블을 그리면 다음과 같다.

Source Code

#include <stdio.h>
int main()
{
    int n,i,j;
    int A[1001]={};
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%d", &A[i]);       
    }
    int dp[1000]={};
    dp[0]=0;
    int max=0;
    //dp table: dp[i]:A[i]를 마지막 값으로 가지는 LIS의 길이
    for(i=0; i<=n; i++)
    {
        for(j=0; j<i; j++)
        {   
            if(A[j]<A[i] && dp[j]+1>=dp[i])
            {
                dp[i] = (dp[j]+1);
                if(max<dp[i])
                    max = dp[i];
            }
        }
    }
    printf("%d", max);
}

첫 번째 반복문: DP 테이블을 채우기 위한 시작 부분
두 번째 반복문: 그 전까지 테이블을 업데이트할 필요가 있는가?에 대한 탐색

dp 테이블의 숫자 중 가장 큰 값이 답이 되기 때문에 최솟값을 찾기 위해 따로 반복문을 돌리는 것이 비효율적이라는 생각이 들어서 반복문 안에서 max 변수를 놓고 업데이트하는 방식으로 최댓값을 찾았다

시간복잡도: O(n^2)
n<1000이니까 1초 안에 가능.