백준 11053번, 1965번, 2565번 파이썬 | 가장 긴 증가하는 부분 수열 관련 문제 (LIS)

문제

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

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

입력

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

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

출력

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

---

풀이

전형적인 LIS 문제이다. LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열이다.

증가하는 수들의 연속이 제일 긴 것을 찾으면 되는데 이 문제는 DP로 쉽게 풀 수 있다.

#11053 가장 긴 증가하는 부분 수열
#LIS

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
DP = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            DP[i] = max(DP[i], DP[j] + 1)
print(max(DP))
#O(n^2)

 

DP[i]번째와 DP[j]+1 중 큰 값을 DP[i]에 넣어주는 식으로 반복하게 되면 가장 긴 수열을 찾을 수 있다.

 

이와 비슷한 문제는 백준 1965번, 백준 11055번이 있다.

---

www.acmicpc.net/problem/1965

1965번: 상자넣기

똑같은 로직으로 사용된다.

#1965 상자넣기
#LIS

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
DP = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            DP[i] = max(DP[i], DP[j] + 1)
print(max(DP))
#O(n^2)

 

---

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

#2565 전깃줄
#LIS

import sys
input = sys.stdin.readline

n = int(input())
wire = {}

for i in range(n):
    a, b = map(int, input().split())
    wire[a] = b
wire = sorted(wire.items())
arr = []
for key, value in wire:
    arr.append(value)

DP = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            DP[i] = max(DP[i], DP[j] + 1)
result = n - max(DP)
print(result)
# O(n ^ 2)

똑같은 로직이 사용되지만 여기서는 전깃줄이 교차되는 선을 제거해 주면 되니까 전체 길이에서 가장 긴 부분 수열의 길이를 빼주면 된다.

 

 

---

배운점 및 느낌점

GSAT CT 공부를 하면서 LIS 풀이법을 알아둔게 문제를 해결하는데 도움이 되었다. 

 

DP를 잘 활용하면 쉽게 해결할 수 있는데 시간 복잡도가 O(N^2)이기 때문에 문제 조건을 잘 보고 사용해야 될 것 같다.

아직 DP 공부가 부족해서 더 많이 공부해야 할듯..