[백준] 11053번 : 가장 긴 증가하는 부분수열

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

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

풀이 1)

먼저 부르트포스 방식으로 2중 for 문을 이용하여 O(n^2)의 시간 복잡도로 문제를 해결 할 수 있다.

dp 테이블을 n-1 개 생성하여 

{1} , {1,5} , {1,5,2} {1,5,2,1}, {1,5,2,1,4} ... {1,5,2,1,4,3,4,5,2}, {1,5,2,1,4,3,4,5,2,1} 로 반복하여

 

- i가 0일때  {1}

    dp[0] = 1

 

- i가 1일때  {1,5}

    dp[1] = 2

 

- i가 2일때  {1,5,2}

    dp[2] = 2

 

- i가 3일때  {1,5,2,1}

    dp[3] = 2

 

- i가 4일때  {1,5,2,1,4}

    dp[4] = max(dp[4], dp[2] + 1) # 4는 {1,5,2} 에서 {1,5,2,4} -> {1,2,4} 이기때문에 dp[2]에서 1을 더한 값으로 업데이트한다.

...

점화식은 이중 for문에서 arr[i] > arr[j] 일때 dp[i] = max(dp[i], dp[j] +1)로 도출 할 수 있다. 즉 i가 3일때 이미 dp[2]는 {1,5,2} 인 상황에서 {1,5,2,4}가 되어진 상황이므로 {1,5,2}의 최대 길이 값은 dp[2] 임으로 2이고, dp[4]는 dp[2]에서부터 1을 증가시킨 값을 가져와 업데이트 할 수 있다.

 

N = int(input())
arr = list(map(int,input().split()))

dp = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)
            
print(max(dp))

풀이 2) 

dp 테이블을 추가/업데이트 할 수 있는 리스트 형태로 구성하여 최종 리스트의 길이를 구하는 방법으로 해결한다.

문제 접근 : 단일 for문으로 arr을 순회하면서 dp테이블을 작은 순열부터 큰 순열까지의 순서대로 넣는다.

만약 dp 리스트의 마지막 idx가 현재 arr순회 값보다 작을 경우 dp 리스트의 idx를 찾아서 해당 값으로 업데이트를 해준다면 최대 길이는 유지 되면서 dp 리스트는 추후 더 긴 수열을 찾을 수 있게 된다.

 

- i가 0일때  {1}

    dp = [1]

 

- i가 1일때  {1,5}

    dp = [1,5]

 

- i가 2일때  {1,5,2} # 5를 2로 바꿔준다.

    dp = [1,2]

 

- i가 3일때  {1,5,2,1}

    dp = [1,2]

 

- i가 4일때  {1,5,2,1,4}

    dp = [1,2,4]

 

- i가 6일때  {1,5,2,1,4,3} #4를 3으로 바꿔준다.

    dp = [1,2,3]

 

- i가 6일때  {1,5,2,1,4,3,4}

    dp = [1,2,3,4]

 

- i가 7일때  {1,5,2,1,4,3,4,5}

    dp = [1,2,3,4,5]

 

- i가 8일때  {1,5,2,1,4,3,4,5,2}

    dp = [1,2,3,4,5]

 

- i가 9일때  {1,5,2,1,4,3,4,5,2,1}

    dp = [1,2,3,4,5]

 

dp 리스트를 i시점에서 길이를 구하면 가장 긴 수열이 나오게된다.

N = int(input())
li = list(map(int,input().split()))
dp = [li[0]]

for i in range(1,N):
    if li[i] > dp[-1]:
        dp.append(li[i])
    else:
        j = len(dp)-1
        while j > 0:
            if dp[j-1] < li[i]:
                break
            j -= 1
        dp[j] = li[i]
print(len(dp))