이번 문제는 이분 탐색을 통해 해결하였다. 처음에 문제를 접했을 때에는 다이나믹 프로그래밍을 통해 풀어야겠다고 생각하였다.

현재 위치의 수 앞을 순회하며 자신보다 작은 수가 있을 경우 dp를 업데이트 시키는 방식으로 작성하였다.

n=int(input())
arr=list(map(int, input().split()))
dp=[0 for _ in range(n)]
for i in range(n):
    if dp[i]==0:
        dp[i]=1
    for j in range(i):
        if arr[i]>arr[j]:
            if dp[i]<dp[j]+1:
                dp[i]=dp[j]+1
print(max(dp))

그러나 DP는 O(N^2)의 시간 복잡도가 소요되었고, N의 범위가 10만을 넘었기 때문에 시간 초과가 발생하였다. 이를 해결할 방법으로 이분 탐색을 이용해야 한다는 사실을 알게 되었다.

그래서 증가하는 수열을 리스트로 구현하기로 하였다. 먼저 0을 넣어두고, 만약 현재 위치의 수가 수열의 가장 뒤의 수보다 클 경우에는 수열의 맨 뒤에 현재 위치의 수를 넣어주고, 그 외의 경우에는 이분 탐색을 통해 현재 위치의 수보다 큰 수를 수열에서 찾아 그 자리를 대체하도록 하였다. 이 풀이는 전체 수열을 순회하는데에 O(N)이 소요되고, 이분 탐색을 진행할 때에 O(log N)이 소요되어 총 O(N log N)이 소요된다.

• n을 입력받는다.
• arr을 입력받는다.
• result 리스트를 0을 넣어 선언한다.
• arr을 순회하는 a에 대한 for문을 돌린다.
  -> 만약 result[-1]이 a보다 작을 경우,
  --> result에 a를 넣는다.
  -> 그 외의 경우,
  --> left, right를 0, result의 길이-1로 선언한다.
  --> left가 right 미만일 동안 반복하는 while문을 돌린다.
  ---> mid를 (left+right)//2로 선언한다.
  ---> 만약 result[mid]가 a보다 작을 경우,
  ----> left를 mid+1로 갱신한다.
  ---> 그 외의 경우,
  ----> right를 mid로 갱신한다.
  --> result[right]를 a로 갱신한다.
• result의 길이-1을 출력한다.

Code

n=int(input())
arr=list(map(int, input().split()))
result=[0]
for a in arr:
    if result[-1]<a:
        result.append(a)
    else:
        left, right=0, len(result)-1
        while left<right:
            mid=(left+right)//2
            if result[mid]<a:
                left=mid+1
            else:
                right=mid
        result[right]=a
print(len(result)-1)