[python] 백준 12738번: 가장 긴 증가하는 부분 수열 3
문제
문제 출처 : https://www.acmicpc.net/problem/12738
수열 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,000,000,000 ≤ Ai ≤ 1,000,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
문제 풀이
접근
최장 부분 증가 수열 LIS 문제이다. 기존에 앞부분을 모두 다시 확인하는 O($N^2$) 방식은 시간 초과가 날 것이다.
풀이
기존에 앞부분을 전부 확인하는 대신 이분탐색으로 현재값이 들어갈 곳을 찾는다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
dp = [1]
x = [a[0]]
for i in range(1, n):
if a[i] > x[-1]:
x.append(a[i])
dp.append(dp[-1] + 1)
else:
idx = bisect_left(x, a[i])
x[idx] = a[i]
print(dp[-1])
후기
현재값이 들어갈 곳을 이분탐색으로 찾아서 바꾼다는게 처음에는 “그럼 어떤 수가 먼저 나왔는지 알 수 없는거 아니야?” 하는 생각을 했다.
하지만 길이만 바뀌지 않으면 값이 변하지 않으므로 정답을 도출할 수 있다.
This post is licensed under CC BY 4.0 by the author.