[baekjoon] 백준 11722번(파이썬): 가장 긴 감소하는 부분 수열

문제

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

알고리즘

- 리스트를 거꾸로 변환해 가장 큰 증가하는 부분 수열의 길이를 구하는 방법으로 바꾸어 문제를 수행한다.

- 반복문을 통해 수열이 증가하는지 확인하고 i번의 수와 이전수를 비교한다.

- 두 수를 비교하고 현재 수가 더 크다면 증가하는 부분 수열의 길이를 구한다.

- 현재 증가한 부분수열보다 비교하고 있는 길이가 크다면 현재 증가한 부분 수열을 비교하고 있는 길이로 초기화한다.

- 반복문이 끝난 후 증가하는 부분 수열의 길이를 증가시킨다.

코드

import sys


n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
m.reverse() # 리스트를 거꾸러 변환해 가장 긴 증가하는 부분 수열의 길이를 구하는 방법을 사용
dp = [1] * n

# 반복문을 통해 수열이 증가하는지 확인
for i in range(1, n):
    temp = 0

    # i번의 수와 이전 수들을 비교
    for j in range(i):
        # 두 수를 비교
        if m[i] > m[j]:
            # 증가하는 부분수열의 길이를 구한다.
            if temp < dp[j]:
                temp = dp[j]

    # 증가하는 부분 수열의 길이를 증가시킨다.
    dp[i] = temp + 1

print(max(dp))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법