[백준(BOJ)] #11053- 가장 긴 증가하는 부분 수열 (파이썬, PyPy3)

문제

 

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

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

 

---

문제 풀이

가장 긴 증가하는 부분 수열은 동적 계획법의 대표적인 문제 중 하나로 LIS(Longest Increasing Subsequence)로 잘 알려져 있습니다.

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

아이디어는 다음과 같습니다.

 

1) 주어진 수열A의 LIS의 길이를 저장할 dp 테이블을 만든다. 이때 모든 수열의 원소는 부분 수열로 자기 자신을 포함하므로 dp 테이블은 전부 1로 초기화한다.

2) 두번째 원소부터 이중 반복문을 돌면서 자기 자신보다 앞에 있으면서 작은 원소들 각각이 속한 부분 수열의 길이에서 1을 더한 값과 자기 자신이 속한 부분 수열의 길이를 비교하여 더 큰 값으로 갱신해간다. (첫 번째 원소까지 속한 부분 수열의 길이는 어차피 1)

 

1) 수열 A가 주어지고 dp테이블을 위와 같이 초기화 한다.

 

2) 20보다 앞에 있으면서 작은 원소는 10이다.

 

10을 가리키는 dp[0] 즉, 10이 속한 부분 수열의 길이는 1이다. 2(10이 속한 부분 수열의 길이 + 1)와 1(자기 자신이 속한 부분 수열의 길이) 중 2가 더 크므로 2로 갱신한다.

 

10이 속한 부분 수열의 길이 + 1의 의미: 10까지 고려한 부분 수열에서 자기 자신까지 포함시켜서 얻을 수 있는 부분 수열의 길이

 

자기 자신이 속한 부분 수열의 길이의 의미: 기존의 자기 자신이 속한 부분 수열의 길이

 

3) 10보다 앞에 있으면서 작은 원소는 없다.

 

4) 30보다 앞에 있으면서 작은 원소는 10, 20, 10이다.

 

10을 가리키는 dp[0] 즉, 10이 속한 부분 수열의 길이는 1이다. 2(10이 속한 부분 수열의 길이 + 1)와 1(자기 자신이 속한 부분 수열의 길이) 중 2가 더 크므로 2로 갱신한다.

 

20을 가리키는 dp[1] 즉, 20이 속한 부분 수열의 길이는 2다. 3(20이 속한 부분 수열의 길이 + 1)와 2(자기 자신이 속한 부분 수열의 길이) 중 3이 더 크므로 3으로 갱신한다.

 

10을 가리키는 dp[2] 즉, 10이 속한 부분 수열의 길이는 1이다. 2(10이 속한 부분 수열의 길이 + 1)와 3(자기 자신이 속한 부분 수열의 길이) 중 3이 더 크므로 갱신하지 않는다.

 

5) 20보다 앞에 있으면서 작은 원소는 10, 10이다.

 

10을 가리키는 dp[0] 즉, 10이 속한 부분 수열의 길이는 1이다. 2(10이 속한 부분 수열의 길이 + 1)와 1(자기 자신이 속한 부분 수열의 길이) 중 2가 더 크므로 2로 갱신한다.

 

10을 가리키는 dp[2] 즉, 10이 속한 부분 수열의 길이는 1이다. 2(10이 속한 부분 수열의 길이 + 1)와 2(자기 자신이 속한 부분 수열의 길이)는 같은 값으로 갱신하지 않는다.

 

6) 50은 앞에 있는 모든 값보다 크다. 앞에 있는 원소들 각각이 속한 부분 수열 길이 + 1과 자기 자신이 속한 부분 수열 길이를 비교하여 갱신한다. 30의 부분 수열 길이가 3(dp[3])으로 앞에 있는 원소들의 부분 수열 길이 중 제일 크므로 4가 된다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if a[i] > a[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    print(max(dp))

결과