알고리즘 - 동적계획법 (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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

---

문제 요약

입력 받은 리스트 중 증가하는 가장 긴 부분 수열

 

접근 방식

현재 값이 이전 값보다 작게 되는 경우 어떻게 처리할 것인지가 중요, 결국 자신보다 작은 값이 있으면 그 값 부터 또 다른 새로운 연속 수열을 검사할 리스트가 있어야 한다.

 

따라서 초반에는 각 인덱스의 갯수에 맞게 리스트를 준비해서 할려 했지만 패스

 

결국 중요한 것은 이전값보다 작은 값이 나타나면 새로운 분기를 맞이 하지만, 최대값을 찾아햐 하기 때문에 if문을 통해 해결

 

 

N = int(input())
n_list = list(map(int, input().split()))
 
arr = [1 for _ in range(N)]
 
for i in range(N):
    for j in range(i):
        if n_list[i] > n_list[j] and arr[i] < arr[j]+1:
            arr[i] = arr[j] + 1
print(max(arr))