가장 긴 증가하는 부분 수열 1 - DP

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

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

조건 수열의 크기는 1 <= 1000

수열의 각 값의 범위는 1 <= 1000

 

가장 긴 부분수열의 길이를 출력한다.

 

해당 문제를 백트레킹 방식으로 모든 조합을 추출하게 될경우

시간복잡도가 O(2ⁿ) 으로 비효율적이다.

 

가장 간단한 방식인 DP 알고리즘으로 접근해본다.

 

이처럼 배열의 크기가 1일때, 가장 큰 부분수열은 10 하나로 1이 출력된다.

배열의 크기가 2 이고, 현재 idx 1을 확인중이다.

왼쪽 표를 보면, 아직 수열이 이어졌는지 확인하기전이므로 20 혼자의 수열이므로 개수 한개를 남겨두었다.

 

Arr[1] 의 크기가 Arr[1-1] 값보다 큰것을 확인할수 있다.

 

그럼 이전의 수열에서 해당값이 수열에 추가될수 있음을 판단할수 있다.

현재까지의 수열의 개수는 기존 수열의 개수 +1 로 2개가 된다.

다음 요소를 보면 상황이 다르다.

기존 수열 (10 - 20) 에 10을 이어주면 안된다는 판단할수 있다.

 

현재의 값 10을 두고 봤을때, 이전값들(10과 20)중에서 이어질수 있는 요소도 없다.

 

만약 첫번째 요소의 값이 9라면 조금 더 달라졌을것이다.

(9 - 20) , (9 - 10) 으로 총 두개의 수열이 확인된다.

 

즉, 해당 문제를 풀기위해 DP식으로 문제를 접근하게 되면,

현재의 값을 기준으로 두고, 앞의 값들과 비교하는 방식으로 진행된다.

 

다시, 0번째 요소를 되돌려놓고 이어가보자.

30의 값은 (10 - 20) 의 수열 뒤에 이어져야 가장 긴 수열이 된다.

하지만, 3번째 요소인 (10-30) 의 수열로 이어질수도 있다.

 

이때, 가장 긴수열을 판단하기 위해선,

앞에서 자신보다 작은 값중에서 가장 긴 수열의 개수를 찾아내면 된다.

(10 - 20) 과 (10) 일때 가장 긴 수열은 20의 2개 인것을 확인할수있다.

 

반복문을 돌려줌으로 배열의 요소중, 자신의 값보다 작으며, 가장 길었던 수열 개수 찾아내기

위와같은 방식으로 배열의 모든요소를 확인하게 되면 가장 긴수열은 4개가 확인된다.

 

풀이

int n = int.Parse(Console.ReadLine());

int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
int[] dp = new int[arr.Length];

dp[0] = 1;

for (int i = 1; i < arr.Length; i++)
{
    for (int j = 0; j < i; j++)
    {
        if(arr[j] < arr[i])
            dp[i] = Math.Max(dp[i] , dp[j]+1);
    }

    if(dp[i] == 0)
        dp[i] = 1;
}

 

 

개선될수 있는 부분이나 미흡한 부분이 있다면 답글 남겨주세요