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

문제

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

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

풀이

18353번 - 병사 배치하기 (tistory.com)

18353번 - 병사 배치하기

위 문제에서 이미 정리한 바 있다. 두 가지 방법으로 풀 수 있다.

• 이중 반복문을 사용한 dynamic programming 접근법.
• 이진 탐색을 활용한 방법.

DP

길이 N의 A 라는 수열이 존재할 때, A[i] 를 포함한 '가장 긴 증가하는 부분 수열' 을 DP로 만든다. 즉 i 보다 작은 j 에 대해서, A[j] < A[i] 일 때 dp[j]+1이 가장 큰 경우를 찾으면 되는 것이다.

N = int(input())
A = [0] + list(map(int,input().split()))

dp = [1]*1001
answer = 1

for i in range(1,N+1):
    for j in range(1,i):
        if A[j] < A[i]:
            dp[i] = max(dp[i],dp[j]+1)
        answer = max(answer,dp[i])

print(answer)

이진 탐색

이진탐색을 활용한 접근법이다. 가장 긴 증가하는 부분 수열을 만든다는 것은, 부분 수열의 맨 뒤 수가 되도록 작아야 한다는 것을 의미하며, 이를 위해 부분수열의 맨 뒤 숫자보다 A[i]가 작거나 같다면 부분 수열에서 이진탐색으로 A[i]가 들어갈 자리를 찾아 그 자리에 있는 부분 수열의 수와 교체한다.

[1, 31, 1, 3, 1, 4] 을 예로 들어 설명해보면, 처음에는 [1, 31] 일 테지만 3을 31과 교체해버리면 뒤의 4 가 올 수 있게된다. 따라서 부분 수열은 [1, 3, 4] 가 될 것이다.

from bisect import bisect_left

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

li = []
li.append(A[0])

for i in range(1,N):
    if A[i] > li[-1]:
        li.append(A[i])
    else:
        li[bisect_left(li,A[i])] = A[i]

print(len(li))