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

문제

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

 

문제 풀이

 기존의 푼 문제 중 가장 긴 증가하는 부분 수열에서 부등호의 방향만 변경하면, 이 문제는 풀 수 있다. 즉 이전 문제의 풀이를 정확히 이해하고 있다면 비슷하게 응용해서 푸는 문제이므로 어렵지 않게 문제를 풀 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))

    answer = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] > nums[i]:
                answer[i] = max(answer[i], answer[j] + 1)
    print(max(answer))