[BOJ] 11053번 가장 긴 증가하는 부분 수열 / 사용언어 : 파이썬

※ 문제링크 

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

※ 관련개념 

[알고리즘]최장 증가 부분 수열 알고리즘(LIS)

이번 문제는 LIS의 개념을 이용하여 풀어야하는 문제였다. LIS가 생소한 개념이라 구글링을 통해 개념을 확인하고 문제를 풀었다. 구체적인 풀이 방법과 코드는 아래와 같다.

1. 입력값을 저장할 리스트와 각각의 요소들의 위치에 가질 수 있는 LIS값을 저장할 리스트를 생성한다.

2. 2번째 원소(n)부터 원소 앞에 해당하는 값(k)들 중 해당 원소(n)보다 작은 원소(k)들의 LIS값을 저장한 후 그 중 최댓값에 1을 더해 해당원소(n)의 LIS값을 갱신한다.(작은 원소가 없을 경우 1을 LIS값으로 갱신)

3. dp리스트의 최댓값을 출력한다.

 

N = int(input())
num_list = list(map(int, input().split()))
dp = [1 for x in range(N)]
i = 1
while i < N:
    check_list = []
    for k in range(i):
        if num_list[k] < num_list[i]:
            check_list.append(dp[k])
        else:
            check_list.append(0)
    dp[i] = max(check_list)+1
    i += 1
print(max(dp))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.