[BOJ/Python] 백준 11052 - 가장 긴 증가하는 수열

문제

https://www.acmicpc.net/problem/11053

문제

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

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

 

입력

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

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

 

출력

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

풀이

N = int(input())

A = list(map(int, input().split()))

dp = [1] * N

for i in range(1, N): # 배열 A의 각 요소 순회, 현재 i
    for j in range(i): # i 이전의 값 순회
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j] + 1)
            # dp[j] + 1은 A[j]까지의 최장 증가 부분 수열의 길이에 A[i]를 추가한 길이

print(max(dp))

 

1. 수열의 길이를 입력받을 리스트 dp를 생성한다.
   원소가 1개만 있어도 길이는 1이므로 1로 초기화한다.
2. 입력받은 배열의 요소를 순회하면서 -> 해당 요소 이전의 값을 반복 순회하고 이동한다.
3. 현재 인덱스(i)의 값보다 j가 작은 경우,
   인덱스의 길이는 현재 길이 혹은 현재 순회중인 값의 길이에 인덱스 길이를 추가한 것 중 큰 값을 선택한다.

풀이 기반 예시

- input: 10 20 10 30 20 50
- 초기화: dp = [1, 1, 1, 1, 1, 1]
i = 1, j = 0: 
    A[1] > A[0] → dp[1] = max(1, 1 + 1) → dp = [1, 2, 1, 1, 1, 1]
i = 2, j = 0, 1: 
    A[2] <= A[0], A[2] <= A[1] → dp = [1, 2, 1, 1, 1, 1]
i = 3, j = 0, 1, 2: 
    A[3] > A[0] → dp[3] = max(1, 1 + 1) → dp = [1, 2, 1, 2, 1, 1]
    A[3] > A[1] → dp[3] = max(2, 2 + 1) → dp = [1, 2, 1, 3, 1, 1]
i = 4, j = 0, 1, 2, 3: 
    A[4] > A[0] → dp[4] = max(1, 1 + 1) → dp = [1, 2, 1, 3, 2, 1]
i = 5, j = 0, 1, 2, 3, 4: 
    A[5] > A[0] → dp[5] = max(1, 1 + 1) → dp = [1, 2, 1, 3, 2, 2]
    A[5] > A[1] → dp[5] = max(2, 2 + 1) → dp = [1, 2, 1, 3, 2, 3]
    A[5] > A[3] → dp[5] = max(3, 3 + 1) → dp = [1, 2, 1, 3, 2, 4]