백준 11053번 가장 긴 증가하는 부분 수열 (Lis) 파이썬 (python code)

난이도: 실버2
번호: 11053번

 

이번 문제는 가장 긴 증가하는 부분수열 LIS를 계산하는 문제이다.

 

www.acmicpc.net/problem/11053

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

 

가장 긴 부분수열은 수열중에서 오름차순으로 뽑을 수 있는 수열중 최대 길이를 갖는 수열으로

 

예시1)

10 20 10 30 20 50 에서 10 20 30 50으로 4

예시2)

10 30 20 30 40 50 80 60 70에서 10 20 30 40 50 60 70 으로 6

예시3)

30 20 10 에서 30 또는 20 또는 10 으로 1

 

이 된다.

 

DP로 문제를 해결했는데 그 이유는 어떤 숫자를 선택하였을때 그 숫자가 해당 수열에 포함되는지 알 수 없었기 때문이다. 가장 작은 숫자를 선택하더라도 그 숫자가 수열에 들어간다는 보장을 할 수 없었다.

 

따라서 첫번째 숫자부터 살펴보면서 그때까지 만들 수 있는 수열의 최대길이를 구하는 방식을 취했다.

10 20 10 30 라는 수열에서 0 0 0 0으로 새로운 llist를 만들고

list[0]=1

list[1]=2

list[2]=2

list[3]=3 이 되도록 프로그래밍하였다.

 

import sys

N = int(sys.stdin.readline().rstrip())
num = list(map(int,sys.stdin.readline().split()))
lis = [0 for i in range(N)]
for i in range(N):
    for j in range(i):
        if num[i] > num[j] and lis[i] < lis[j]:
            lis[i] = lis[j]
    lis[i] += 1
print(max(lis))