백준 11053번: 가장 긴 증가하는 부분 수열 (최적화X)

[www.acmicpc.net/problem/11053]

#풀이

- 기본적인 동적 계획법이다.(최적화는 다른 문제 에서...)

1. 수열을 담을 배열과 해당 숫자까지 증가하는 길이를 담을 배열을 준비한다.

2. 반복문을 돌면서 어떤 수 전까지의 수열에서 가장 긴 길이 + 1 을 한다.

1 2 3 4 5 6 7 8 9 10 11

import sys input = lambda : sys.stdin.readline().rstrip() n=int(input()) arr=list(map(int,input().split())) count=[1 for _ in range(n)] for i in range(1,n):     for j in range(i):     #어떤수arr[i] 이전 배열에서 가장 긴 수열 +1 을 한다         if arr[i]>arr[j] and count[j] >= count[i]:             count[i]=count[j]+1 print(max(count)) Colored by Color Scripter

cs