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

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

해설

 '가장 긴 ~ 하는' 시리즈의 문제이다. 우선 문제를 보았을 때 '연속적'으로 감소하는 수열의 길이를 구한다는 점에서, 다이나믹 프로그래밍을 이용하지 않을까 유추해볼 수 있다. 주로 이런 수열 패턴의 문제가 '이전의 답' 을 활용해 다음 답을 결정해나가기 편리하기 때문이다.

 

 이 문제에서 DP 리스트는 'i번 원소까지 보았을 때 가장 긴 감소하는 수열의 길이' 로 정의하였다. 예를 들어, {5, 3, 4, 2, 1} 이라는 수열이 있다고 치자.

 

• DP[0] 은 수열의 0번째까지 보았을 때 (={5})
• DP[1] 은 수열의 1번째까지 보았을 때 (={5, 3})
• DP[2] 은 수열의 2번째까지 보았을 때 (={5, 3, 4})
• (생략)...

로 보는 것이다. 그러면 이 수열에 대한 DP는 [1, 2, 2, 3, 4] 가 된다.

 

아래는 구현 결과다.

코드

N = int(input())
arr = list(map(int, input().split()))
DP = [1] * (N)

for i in range(N):
    for j in range(i+1, N):
        if arr[i] > arr[j]:
            DP[j] = max(DP[i] + 1, DP[j])
print(max(DP))