백준 | 11053 - 가장 긴 증가하는 부분 수열 (python)

📈 가장 긴 증가하는 부분 수열

LIS(Longest Increasing Subsequence)를 구하는 문제

 

 

---

✏️ 문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

---

💡 해결방법

수열 a =  {10, 20, 10, 30, 20, 50} 와 부분 수열의 길이를 저장하는 d 배열(모두 1로 초기화)이 있다.

각각의 수는 전 수와 비교하면서 전의 수보다 크면 +1을 하고 비교하며 d를 채워나가면 된다.

 

a[1]	20부터 계산을 할 때, 20(a[1])은 10(a[0])보다 크므로 d[1] = d[0]+1 = 2 를 저장할 수 있다.
a[2]	10은 10(a[0])보다 크지 않으므로 그대로 d[2] = 1 10은 20(a[1])보다 크지 않으므로 그대로 d[2] = 1
a[3]	30은 10(a[0])보다 크므로 d[3] = d[0]+1 = 2 30은 20(a[1])보다 크므로 d[3] = d[1]+1 = 3 (앞의 계산으로 d[3]은 2가 되었지만 3이 더 크므로 3을 저장한다.) 30은 10(a[2])보다 크므로 d[3] = d[2]+1 = 2이지만 앞의 계산으로 구한 d[3]값이 3이므로 큰 값인 3을 저장한다.
	...
a[n]	위와 같은 방법으로 계속해서 전 값과 비교하며 계산

 

위와 같이 계산을 하면 d값이 채워지고 가장 큰 값을 출력하면 된다.

즉 점화식은 다음과 같다.

d[i] = max(d[i], d[j]+1)
i는 현재 값의 인덱스, j는 비교해나가는 전 값의 인덱스

 

 

👩🏻‍💻 소스코드

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
d = [1 for _ in range(n)]

for i in range(n):
    for j in range(0, i):
        if a[j] < a[i]:
            d[i] = max(d[i], d[j]+1)

print(max(d))

 

 

---

 

 

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