알고리즘 스터디
[백준] 14002 : 가장 긴 증가하는 부분수열 - Python(파이썬)
히치키치
2021. 5. 3. 16:41
문제
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
풀이
- 동적 계획법
- 길이 : 일차원 배열에 당시 길이 최대값 유지/갱신 : 이전 수+1
- 수열 출력 : 배열에 최대값 가진 인덱스부터 -1 하며 원래 수열에서 해당 값 가져오기
코드
n = int(input())
arr = list(map(int, input().split()))
max_len = [1]*n
for i in range(1, n):
for j in range(i):
if arr[i]>arr[j]:
max_len[i] = max(max_len[i], max_len[j]+1)
print(max(max_len))
curr_max = max(max_len)
lst = []
for i in range(n-1, -1, -1):
if max_len[i]==curr_max:
lst.append(arr[i])
curr_max-=1
lst.reverse()
for i in lst:
print(i, end=' ')