[Python Algorithm] Dynamic programming(동적계획법) - 최대 부분 증가수열

> Dynamic programming(동적계획법)

 

 

 

 

 

📖 문제 :  최대 부분 증가 수열

 

 

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다. 

 

 

 

입력설명

첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다. 

 

출력설명

 

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다. 

 

입력예제 1

 

8

5 3 7 8 6 2 9 4 

 

출력예제 1

4 

 

 

 

내 코드

 

if __name__ == "__main__":

    n = int(input())
    num = list(map(int,input().split()))
    result = [0]*n
    result[0]=1
    
    for i in range(1,n):
        t = False
        maxx = 0
        for j in range(0, i):
           if num[i] > num[j] and maxx < result[j]:
               maxx = result[j]
               t = True
               
        if t == False:
            result[i] = 1
        else:
            result[i] = maxx+1
            
        t = False
        maxx = 0

    print(max(result))

 

 

Point ! ⭐️ 

• 자신보다 더 작은 숫자가 있으면 그 숫자가 구해둔 가장 최대 증가수열의 수+1을 넣어주면 된다.
  예를 들어
  8
  5 3 7 8 6 2 9 4 에서
  8 입장에서 보면
  5의 최대 증가 수열 = 1
  3의 최대 증가 수열 = 1
  7의 최대 증가 수열 = (5, 7) 또는 (3, 7)로 5의 값 1 + 1 또는 3의 값 1 + 1 = 2 가 되고
  8의 최대 증가 수열은 값 5, 3 보다 7이 구한 증가 수열이 가장 2로 크므로 2 + 1 = 3이 되는 것 !
  
  
   

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이