[백준] 11722. 가장 긴 감소하는 부분 수열

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

 

가장 큰 증가하는 부분 수열 문제와 굉장히 유사하여 풀이 설명도 거의 비슷하게 했다.

 

주어진 수열에서 감소하는 일부분들의 길이 중 그 길이가 최대가 될 수 있는 경우를 구해야 하는 문제이다.

 

※ 예시

수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

 

입력받는 수열을 a라고 하고

d[i]는 a[i] 이전 숫자들을 보았을 때 a[i]를 포함하여 나올 수 있는 수열 중 가장 긴 수열의 길이로 두었다.

 

이제 점화식을 생각해내야 하는데, d[i]를 구하기 위해서는 a[0]~a[i-1] 중 a[i]보다 더 크면서(이때 더 큰 숫자의 인덱스를 j라고 가정) d[j]가 최대인 값을 찾아야 한다. 찾은 j번째 숫자 다음으로 i번째 숫자가 오면 i번째 숫자를 포함하여 나올 수 있는 감소하는 부분 수열의 길이가 도출 가능해진다(0번째부터 i번째 숫자까지만 보았을 때). 식으로 나타내면

d[i] = d[j] + 1

인 것이다.

 

만약 a[i]보다 크면서 d[j]가 최대인 인덱스가 없으면(= a[i]보다 큰 숫자가 없으면) 감소하는 수열의 시작 부분이 되는 것이므로

d[i] = 1

위와 같이 식을 작성할 수 있다.

 

---

C

#include <stdio.h>
#include <string.h>

int a[1000];
int d[1000];

int findBiggerNum(int v){
    int res = -1, max = 0;
    for(int i = v; i >= 0; i--){
        if(a[i] > a[v])
            if(d[i] > max){max = d[i]; res = i;}
    }
    return res;
}
int findMax(int l){
    int max = 0;
    for(int i = 0; i < l; i++)
        if(d[i] > max) max = d[i];
    return max;
}

int main() {
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    d[0] = 1;
    for(int i = 1; i < n; i++){
        int biggerNum = findBiggerNum(i);
        if(biggerNum != -1)
            d[i] = d[biggerNum] + 1;
        else
            d[i] = 1;
    }
    printf("%d", findMax(n));
}

---

Python

def findBiggerNum(v):
    res = -1
    mx = 0
    for i in range(v, -1, -1):
        if a[i] > a[v]:
            if d[i] > mx:
                mx = d[i]
                res = i
    return res

n = int(input())
a = list(map(int, input().split()))

d = [0 for _ in range(n)]
d[0] = 1

for i in range(1, n):
    biggerNum = findBiggerNum(i)
    if biggerNum != -1:
        d[i] = d[biggerNum] + 1
    else:
        d[i] = 1

print(max(d))