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

 

문제

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

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

 

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

풀이

 

처음에는 변수에 현재까지 가장 길었을 때의 길이와, 그때의 큰 값을 이용해 풀려고 했지만, 변수가 몇개나 필요할지도 알 수 없기 때문에 리스트를 이용했다.

 

수열의 크기 N과 길이가 같은 리스트를 만들고 i번째 수를 a라고 할 때, i번째 이전의 수 중 a보다 작은 수를 구하고 그 수 중에서 횟수가 가장 많은 수에 1을 더해 i번째 리스트에 값을 저장했다.

 

그리고 리스트에 저장된 값 중 가장 큰 값을 구했다. 문제를 풀면서 수열의 크기 N이 1000이라 시간복잡도 O(N)=N^2이지만 풀릴 것이라고 생각했다.

 

 

Code

 

 

N=int(input())
lst=list(map(int,input().split()))
ans=[1]*N
for i in range(N):
    for j in range(i):
        if lst[i]>lst[j]:
            c=ans[j]+1
            if ans[i]<c:
                ans[i]=c
print(max(ans))

 

---

 

시간복잡도가 N^2이라서 다른 사람들은 어떻게 풀었는지 봤는데, 리스트에 연속된 수열의 값을 추가하면서 구했다.

 

현재 수가 리스트의 마지막 수보다 크면 리스트에 추가하고 만약 작다면, 이진 검색과 같은 방법으로 리스트에서 같은값이나, 비슷한 값을 찾아 그 위치에 덮어쓰기를 했다.

 

이 과정을 반복하면 리스트의 마지막 값을 덮어쓰기 전에는 리스트의 길이가 최대 연속 수열의 길이이고 덮어써진 후에는 이전 리스트 값보다 마지막 값이 작으면서 길이는 같으므로 가장 긴 증가하는 부분 수열로 덮어써지는 것이다.

​

만약 N의 크기가 컸다면 시간초과로 문제를 풀기 위해 시간이 좀 걸렸을 것 같다.

 

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