[BEAKJOON] 백준 11053번 : 가장 긴 증가하는 부분 수열 - 파이썬

문제

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

 

문제 설명

 

STEP 1 ] 변수 선언

DP 테이블을 사용해서, 모두 1로 초기화해준다.

 

STEP 2 ]

주어진 숫자의 배열에서 인덱스를 하나씩 늘려서 LIS(Longest Increasing Subsequence) 를 찾는다.

인덱스는 1부터 N까지 진행한다.

( 0번째 인덱스의 값은 길이가 무조건 1이다.)

 

STEP 3 ]

이중반복문을 이용하여 길이의 값은 이전값들과 비교하여 LIS 배열값을 갱신해준다.

 

핵심은, 길이를 찾으려는 숫자가 비교할 숫자보다 크면, 그 숫자가 가지고 있는 길이 +1 과 자신의 길이를 비교해서 큰 값으로 최신화 한다. 

 

 

문제 정답 코드

import sys

num = int(input())

num_list = list(map(int, sys.stdin.readline().split()))

result_list = [1]*num

for i in range(1, num):
    for j in range(i):
        if(num_list[j] < num_list[i]):
            result_list[i] = max(result_list[i], result_list[j]+1)

print(max(result_list))