[Python] Baekjoon - 11053. 가장 긴 증가하는 부분 수열

백준 11053번 가장 긴 증가하는 부분 수열은 다이내믹 프로그래밍(DP)을 이용해서 풀 수 있는 문제이다. 난이도는 실버 2로, DP를 이용해 효율적으로 푸는 방법을 떠올리기 어려운 문제다. 길이가 N인 수열에 등장하는 증가하는 부분 수열 중 가장 길이가 긴 것의 길이 구한다.

 

가장 긴 증가 부분 수열 문제 정보

알고리즘 분류

- 다이나믹 프로그래밍

난이도

- 실버 2

요약

길이가 N인 수열에 등장하는 증가하는 부분 수열 중 가장 길이가 긴 것의 길이 구하기

문제 풀이 과정

• 각 위치의 숫자를 포함하는 증가 부분 수열의 최대 길이를 저장하는 배열을 사용한다.
• 현재 숫자보다 작으면서, 가장 긴 증가 부분 수열을 갖는 부분 수열의 뒤에 추가한다.

풀이

• cnt[i]: i번째 숫자를 포함하는 증가 부분 수열의 길이의 최댓값
• cnt[i]를 구할 때, 1 ~ i-1사이의 값 j에 대해 num_list[i] > num_list[i]이면서 가장 큰 cnt[j]값을 이용해 cnt[i] = cnt[j] + 1로 저장

코드

def get_longest_list():
    global N, num_list, cnt

    for i in range(N):
        for j in range(i):
            if num_list[j] < num_list[i] and cnt[j] >= cnt[i]:
                cnt[i] = cnt[j] + 1

    return max(cnt)


if __name__ == '__main__':
    N = int(input())
    num_list = list(map(int, input().split()))
    cnt = [1 for _ in range(N)]
    print(get_longest_list())