[Python]11722번, 가장 큰 증가하는 부분 수열

목차

 

문제

 

수열 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. dp리스트 초기화
   우선, dp 리스트를 초기화한다. 이 리스트는 주어진 수열의 각 위치에서 최장 감소 부분 수열의 길이를 저장하는 데 사용될 것이다.
   우선 모든 위치에서의 길이를 1로 초기화한다.
   왜냐하면 어떤 수도 자체적으로 감소하는 부분 수열의 시작점이 될 수 있기 때문이다.
2. 이중 반복문을 이용한 탐색
   핵심 아이디어는 각 위치를 순회하며 현재 위치의 숫자보다 작은 숫자를 찾아내고,
   그중 가장 긴 감소 수열 길이를 찾아 1을 더해 dp를 갱신하는 것이다.
   조금 더 구체적으로 말하자면, 리스트를 처음부터 끝까지 순회하며 각 위치에서 다시 처음부터 현재 위치까지의 숫자를 비교한다.
   만약 현재 위치의 숫자보다 작은 숫자를 발견하면 해당 위치의 dp값을 확인하고, 그 최댓값에 1을 더한 값과
   현재 위치의 dp값과 비교해 큰 값으로 갱신한다.
3. 결과 출력
   리스트를 전부 순회한 이후엔 dp 리스트의 최댓값을 찾아 출력한다.

계속해서 주어진 예시 A = {10, 30, 10, 20, 20, 10}를 실제로 푸는 방법을 살펴보자.

 

1. dp = [1, 1, 1, 1, 1, 1]로 초기화
2. 두 번째 숫자 30은 첫 번째 숫자 10보다 크기 때문에 감소 부분 수열 불가
3. 세 번째 숫자 10은 두 번째 숫자 30보다 작기 때문에 1을 더해 2로 갱신 -> dp = [1, 1, 2, 1, 1, 1]
4. 네 번째 숫자 20은 두 번째 숫자 30보다 작기 때문에 1을 더해 2로 갱신 -> dp = [1, 1, 2, 2, 1, 1]
5. 다섯 번째 숫자 20은 두 번째 숫자 30보다 작기 때문에 1을 더해 2로 갱신 -> dp = [1, 1, 2, 2, 2, 1]
6. 여섯 번째 숫자 10은 네 번째 숫자 20보다 작기 때문에 2를 더해 3으로 갱신 -> dp = [1, 1, 2, 2, 2, 3]

이렇게 해서 답이 3이 되는 것이다.

 

Python

 

import sys

N = int(sys.stdin.readline().rstrip())
lst = list(map(int, sys.stdin.readline().rstrip().split()))

dp = [1] * N

for i in range(N):
    for j in range(i):
        if lst[i] < lst[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))