11722. 가장 긴 감소하는 부분수열

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

11722번: 가장 긴 감소하는 부분 수열

 

이 문제는 이 전에 한 11053. 가장 긴 증가하는 부분수열 (https://tose33.tistory.com/18)과 거의 똑같다.

 

가장 긴 증가하는 부분수열 문제에서

가장 긴 증가하는 부분수열

A[i]값보다 작은 A값 들 중 가장 큰 d값에서 1을 더한것이 D[i]였다.

예를들어 i = 4일때, 수열은 {10, 20, 10, 30} 이고,

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

+1 해주면 3.

d[4] = 3 이었다.

 

---

이번 문제에서는 반대로 A[i]값보다 큰 A값 들 중 가장 큰 d값에서 1을 더한것이 D[i]이다.

가장 긴 감소하는 부분수열

예를들어 i = 4일때, 수열은 {10, 30, 10, 20} 이고,

A[4] = 20보다 큰 값은 A[2]. 그리고 D[2] = 1.

+1 해주면 3.

d[4] = 2.

 

코드

n = int(input())

d = [1] * n
a = [0] * n
a = input().split()

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

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)

j의 for루프에서 a[j] > a[i]

이부분 만 바뀜.

 

---

Solution

 

코드

d = [0] * 1001

n = int(input())
a = input().split()
for i in range(n): a[i] = -1 * 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)

솔루션에서는 원소값들을 입력 받을때 -1 을 곱해줬다.

 

10 20 30 40 50 : 증가 하고 있다

-10 -20 -30 -40 -50 : 감소 하고 있다