11053. 가장 긴 증가하는 부분수열

 

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

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

Longest Increasing Subsequence(LIS) 라는 유명한 문제라고 한다.

 

A[n]에 수열을 넣고,

d[n] : n까지의 가장 긴 증가하는 부분 수열의 길이. 여기서 d[n]은 A[n]을 포함해야 한다.

 

d[1]은 1까지의 가장 긴 증가하는 부분 수열의 길이이다.

A[1]밖에 없으므로 D[1]은 그냥 1이다.

 

d[2]는 2까지의 가장 긴 증가하는 부분 수열의 길이.

즉 수열은 {10, 20}.

20보다 작은 값은 a[1]인 10 하나이고, d[1]은 1. 

d[1]에서 길이가 1증가 하므로 +1 해주면 d[2] = 2.

 

d[3]은 3까지의 까지의 가장 긴 증가하는 부분 수열의 길이. (d[3]은 A[3]을 포함해야함!)

수열은 {10, 20, 10}.

A[3] = 10 보다 작은 값은 없다. 

그래서 A[3]만을 갖기 때문에 d[3] = 1.

 

d[4]는 4까지의 가장 긴 증가하는 부분수열의 길이.

수열은 {10, 20, 10, 30}.

A[4] = 30보다 작은 값은 A[1], A[2], A[3]. 이것들의 d값중 가장 큰 값은 d[2] = 2.

+1 해주면 3. 

d[4] = 3.

 

d[5]는 5까지의 가장 긴 증가하는 부분 수열의 길이.

수열은 {10, 20, 10, 30, 20}.

A[5] = 20보다 작은 값은 A[1], A[3]. 둘다 d값은 1이므로 +1 해주면

d[5] = 2.

 

d[6]은 6까지의 가장 긴 증가하는 부분수열의 길이.

수열은 {10, 20, 10, 30, 20, 50}.

A[1] ~ A[5] 모두 A[6]보다 작기때문에 어떤 값이든 올 수 있다.

가장 큰 d값은 3이므로 1더하면 

d[6] = 4.

 

코드

n = int(input())

d = [1] * n  # 기록할 배열
a = [0] * n  # 수열 저장할 배열
a = input().split()

for i in range(n):  # str로 입력한 배열들 int로 변경
    a[i] = int(a[i])

# d[j]가 i까지 돌면서 i보다 작은지 비교.
# 작으면 length 갱신하고 j 루프 빠져 나가면 d[i]에 length+1 저장.
# i 루프 진행하면서 max_length와 d[i] 계속 비교하면서 max_length도 최대값으로 갱신
max_length = 0
for i in range(n):
    length = 0
    for j in range(i):
        if a[j] < a[i]:
            length = max(d[j], length)

    d[i] = length + 1
    max_length = max(max_length, d[i])

print(max_length)

---

Solution

 

코드

d = [0] * 1001

n = int(input())
a = input().split()
for i in range(n): a[i] = int(a[i])

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

print(res)