|
n = int(input())
l = list(map(int, input().split()))
order = [0 for i in range(n)]
for after in range(n) :
for before in range(after) :
if l[after] > l[before] and order[after] < order[before] :
order[after] = order[before]
order[after] = order[after] + 1
print(max(order))
|
길이 n의 0으로 된 order 테이블을 만든다.
리스트의 모든 원소에 대해, 자기보다 이전 index이면서 값이 작은 원소를 탐색한다.
그 원소의 order가 현재 자신의 order보다 크다면, 자신의 order를 그 값 + 1로 만든다.
결과적으로 모든 원소는 자기보다 작고 앞서있는 원소가 포함된 증가수열 중 가장 긴것의 다음 항이 된다.
for문 종료 후 order 테이블 전체에서 값이 가장 큰 order를 찾으면 그것이 가장 긴 증가수열의 길이이다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 12015 가장 긴 증가하는 부분 수열 2 (0) | 2021.11.17 |
|---|---|
| 파이썬 백준 11722 가장 긴 감소하는 부분 수열 (0) | 2021.11.17 |
| 파이썬 백준 11053 공유기 설치 (0) | 2021.11.16 |
| 파이썬 백준 13334 철로 (0) | 2021.11.16 |
| 파이썬 백준 1715 카드 정렬하기 (0) | 2021.11.15 |