문제

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

풀이 아이디어

DP적으로 접근하기
[10,20,10,30,20,50] 입력값이 주어지면
부분적인 최적을 보는데 예를 들어서

[10]의 가장 긴 증가하는 부분 수열을 구하고
[10,20]의 가장 긴 증가하는 부분 수열을 구하고
[10,20,10]의 가장 긴 증가하는 부분 수열을 구하고
[10,20,10,30]의 가장 긴 증가하는 부분 수열을 구하고
[10,20,10,30,20]의 가장 긴 증가하는 부분 수열을 구하고
[10,20,10,30,20,50]의 가장 긴 증가하는 부분 수열을 구하는 식으로 접근했다.

왜 DP인가?

DP는 '부분의 최적이 전체의 최적일 것이다.'라는 가정으로 접근한다.
원소 2개가 있었고 이후 다음 원소가 추가되었을 때 이전 원소들보다 더 큰 수가 나온다면
원소 3개의 최대 길이는 '원소 2개일 때 '증가하는 부분집합의 최대 길이'+1이다.
이런 방식은 기존 계산 결과를 이용하고 부분의 최선의 선택이 전체의 최선이 선택이 될 것이라는
DP적 사고와 동일하다.

테스트 케이스

# 입력 1
4
3 2 1 4
# 출력 1
2

# 입력 2
4
1 2 3 4
# 출력 2
4

# 입력 3
4
4 3 2 1
# 출력 3
1

풀이 코드

import sys
input = sys.stdin.readline

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

개선할 점

1. 시간복잡도
   입력되는 배열의 길이가 n이고
   0~n-1인덱스를 돌면서 만약에 i가 n-1일 때
   0부터 n-2까지 돌며 큰지 작은지 확인하므로
   확인하는 경우의 수는 $(n-1)\times(n-2) = n^2-3n+2$이므로
   최악 시간복잡도는 $O(n^2)$이 된다.
   다른 논리로 문제에 접근하면 더 짧은 시간에 해결할 수 있을 것 같다.

=> 예를 들어 이분 탐색으로 해결한다면 $O(nlogn)$의 시간복잡도를
가지게 될 것 같다.
나중에 이 방식으로 풀어봐야겠다.