백준 11053 [가장 긴 증가하는 부분 수열] 문제풀이

문제 

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

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

 

 

 

문제 접근 방식

풀이 접근

가장 긴 증가하는 부분 수열을 찾기 위해서는 특정 항을 기준으로 생각했을 때, 자신보다 작은 항의 개수를 찾아야한다. 

완전탐색으로도 일일히 만들어서 풀 수도 있으나 경우의 수가 너무 많아서 시간 초과가 발생할 것 같다. 

 

완전 탐색으로 접근하기 보다는 어쨋든 이전 항들과의 연관성이 있는 것을 알 수 있기에 DP로 문제를 풀 수 있을 것 같다. 

이제 점화식을 구해보자

 

점화식

점화식을 어떻게 정의해야할까?

문제를 풀다보니 약간의 공통점을 발견할 수 있었는데, 점화식을 정의할 때 'i 번째 까지의 최댓값' 이런 식의 정의 보다는 'i 번째를 포함하여 만들 수 있는 i 번째까지의 최댓값' 이런식으로 정의를 해야하는 것 같다(개인적인 의견). 'i 번째를 포함해서' 라는 정의를 포함할 때 이전 항과 연관지어 생각할 수 있다.

 

이 문제의 점화식을 아래와 같이 정의 했다.

d[ i ] = i 번째를 포함해서 만들 수 있는 부분 수열 길이의 최댓값

 

d[ i ] = i 번째를 포함해서 만들 수 있는 부분 수열 길이의 최댓값

 

d[ i ]를 구하기 위해서는 현재 항의 숫자보다 작은 항을 탐색해서, 그 중 부분 수열의 길이가 최댓값인 것에 +1 을 해주면 i 번째를 포함한 가장 긴 부분 수열의 길이를 구할 수 있다.

 

d[ i ]= max ( d [ j ] +1 if nums[ j ] < nums[i] ) ( j < i )

 

 

이렇게 모든 i 에 대해 d[ i ]를 구하고 이 중 최댓값을 구하면 전체 수열에서 가장 긴 부분 수열의 길이를 구할 수 있다.

 

 

시간 복잡도

for 문으로 돌면서 특정 항에 대한 메모이제이션을 해야한다. 또한, 각 항의 d[ i ]를 구하기 위해서는 이전 항에서 자신 보다 작은 행을 탐색해야하기 때문에 내부에서 for문을 돌려야한다. 그렇기 때문에 시간복잡도는 O(n^2) 이고, n 의 최댓값이 1000이기 때문에 시간내에 동작함을 알 수 있다.

 

 

코드

if __name__=='__main__':
    n=int(input())
    li=list(map(int,input().split()))


    # d[i]=i 번째를 포함해서 만들 수 있는 가장 긴 수열의 길이
    d=[0]*n
    d[0]=1
    for i in range(1,n):
        max_value=1
        for j in range(i):
            if li[j]<li[i]:
                max_value=max(max_value,d[j]+1)
        d[i]=max_value

    print(max(d))

 

 

회고

점화식  d[ i ] 를 정의할 때 단순히 ' i 번째까지의 최댓값' 이런식으로 정의를 하기 보다는, 

'nums[ i ] 를 활용한 i 번째의 최댓값' 이런식으로 한다고 알고 있으면 좀 더 쉽게 점화식을 정의할 수 있을 것 같다.