[백준 11722 파이썬/python] 가장 긴 감소하는 부분 수열

가장 긴 감소하는 부분 수열

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	28484	17901	14625	63.809%

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 30 10 20 20 10

예제 출력 1

3

풀이

n = int(input())
a = list(map(int,input().split()))
d = [0] * n
for i in range(n):
    d[i] = 1
    for j in range(i):
        if a[i] < a[j] and d[j] + 1 > d[i]:
            d[i] = d[j] + 1
print(max(d))

이 코드는 주어진 수열에서 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)의 길이를 구하는 알고리즘입니다. 이것을 동적 프로그래밍(Dynamic Programming) 방식으로 구현한 코드입니다. 코드의 구현과정은 다음과 같습니다:

1. n = int(input()) : 수열의 길이 n을 입력 받습니다.

2. a = list(map(int,input().split())) : 공백으로 구분된 n개의 정수로 이루어진 수열 a를 입력 받습니다.

3. d = [0] * n : 수열 a의 각 원소에 대해 길이를 저장할 동적 프로그래밍 테이블 d를 초기화합니다.

4. for i in range(n): 수열 a의 각 원소를 순회하는 외부 루프입니다. a. d[i] = 1 : 가장 긴 증가하는 부분 수열의 최소 길이는 1이므로, d[i]의 초기값을 1로 설정합니다. b. for j in range(i): i 이전의 원소들을 순회하는 내부 루프입니다. c. if a[i] < a[j] and d[j] + 1 > d[i]: 현재 원소 a[i]가 이전 원소 a[j]보다 크고, 이전 원소의 가장 긴 증가하는 부분 수열 길이(d[j])에 1을 더한 값이 현재 원소의 가장 긴 증가하는 부분 수열 길이(d[i])보다 크다면, d. d[i] = d[j] + 1 : 현재 원소의 가장 긴 증가하는 부분 수열 길이(d[i])를 이전 원소의 가장 긴 증가하는 부분 수열 길이(d[j])에 1을 더한 값으로 갱신합니다.

5. print(max(d)) : 동적 프로그래밍 테이블 d의 최대값을 출력합니다. 이 값이 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이입니다.

Uploaded by N2T