[파이썬] 단계별 백준 문제 풀기 - 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

<<소스코드>>

import sys

n = int(sys.stdin.readline()) #수열의 크기
arr = list(map(int,sys.stdin.readline().split())) #주어지는 수열 리스트

# 수열 각각의 최대 증가수열 길이를 저장하는 리스트 생성, 1로 초기화하여 수열 개수만큼 생성
result = [1] * n  #result = [1 1 1 1 1]

# 수열 N개를 하나씩 for문을 통해 반복
for i in range(n):
        for j in range(i): 수열의 비교대상을 위해 for문 반복
                #만약 기준 대상(i)이 이전 비교대상(j)보다 크면서, 비교대상(j)의 result 값이 i보다 크거나 같을 경우
				if arr[j] < arr[i] and result[i] <= result[j]:
                #만약 수열의 30의 arr[3] 경우, 첫번째 조건은 만족하지만 result[3]=3 > result[2]=2 조건 만족X
              
                                result[i] = result[j] + 1
                                
print(max(result)) #result의 값 중 가장 큰 값을 출력

 

<<결과값>>

6
10 20 10 30 20 50

4

---

예제의 수열을 표로 만들어보았다. 각 수열의 초기 result 값을 1로 설정했다. result는 각 수열의 값이 가지는 가장 긴 수열의 길이이다. 우리는 가장 긴 증가 부분 수열의 값을 구해야하기 때문에 4가 출력된다. 

 

10의 경우, 자기 자신밖에 없다(비교대상이 없다). 그래서 자신의 값 1만 갖는다 {10}

20의 경우, 이전값인 10과 비교했을 때, 아래 첫째줄 조건을 만족한다. i가 1이므로 arr[1] = 20 이고, j는 0까지의 범위밖에 못갖기 때문에 arr[0] = 10이다. 즉, 10 < 20 을 만족하고 비교수열의 result값이 1이므로 두번째 조건도 만족한다.

30의 경우, 이전값들인 10,20,10과 비교했을때 값이 크므로 첫번째 조건을 만족한다. 다만 30은 10과 비교할 때 두번째 조건을 만족시키지 못한다. 그래서 20의 result 값에 1을 더해준다. 

if arr[j] < arr[i] and result[i] <= result[j]:           
 	result[i] = result[j] + 1

마지막 조건 result[i] < = result[j] 조건이 없어서 오류가 계속 났다. 30같은 수가 있기 때문에 2번째 조건도 꼭 추가해줘야한다!!!  ✿˘◡˘✿