[BOJ 12015 🥇2] 가장 긴 증가하는 부분 수열 2 (Python)

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

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

 

⭕ CODE

from bisect import bisect_left

n = int(input())
arr = list(map(int, input().split()))

d = []
# dp 배열에 arr[0] 추가
d.append(arr[0])

# i가 0인 arr[0]은 이미 dp배열에 들어갔으므로 1부터 조사
for i in range(1,n):
    # 현재위치의 arr값이 이전 원소보다 크다면
    if arr[i] > d[-1]:
        # dp 배열에 추가
        d.append(arr[i])
    # 작거나 같다면
    else:
        # 이전 위치의 원소 중 가장 큰 원소의 index값을 구하고
        idx = bisect_left(d,arr[i])
        # 그 index의 원소를 arr[i]로 바꿔준다.
        d[idx] = arr[i]

print(len(d))

✏️ Comment

LIS(가장 큰 증가하는 부분수열)문제이다. 이 문제는 N<= 1000000이라서 2중for문을 사용하게되면 시간초과가 난다.
그래서 사용하는것이 바로 이분탐색이다.

풀이법은 다음과 같다.
1. dp[0]을 arr[0]으로 설정
2. arr을 순회하며 arr[i]가 dp의 마지막 값보다 크다면 증가하므로 dp에 추가
3. dp의 마지막 값보다 작거나 같다면 bisect_left로 이전 위치의 원소 중 가장 큰 원소의 index값을 구한다.
4. dp[index] 값을 arr[i]로 변경해준다.
5. dp의 길이를 구한다.

아래 예시를 통해서 설명하고자한다.

6
10 40 20 30 20 50​

 

이 예시를 보면 가장 큰 증가하는 부분 수열은 10 20 30 50 으로 길이가 4가 된다. 

처음 dp[0]은 arr[0]으로 지정

10

현재 index 를 빨간색으로 표시 i =0 은 이미 조사했으므로 i = 1인 40부터 조사하자

10

40

20

30

20

50

arr[i](40)이 dp[-1](10) 보다 크므로 dp 배열에 추가

10

40

 

10

40

20

30

20

50

arr[i](20)이 dp[-1](40) 보다 작으므로 bisect_left를 사용하여 index를 조사하면 1이 나오므로 d[1]을 20으로 갱신

10

20

arr[i]30의 경우는 dp[-1]20보다 크므로 바로 추가

10

20

30

arr[i] 가 20인 경우

10

40

20

30

20

50

dp[-1](30) 보다 작으므로 bisect_left를 사용하여 index를 조사하면 1이 나오므로 20을 d[1]을 20으로 갱신

10

20

30

arr[i]가 50인 경우

10

40

20

30

20

50

dp[-1]값 보다 크므로 dp에 추가

10

20

30

50

이 나오게 된다.

dp의 길이인 4가 정답이 된다.