[Python] 백준 14002번 문제, 가장 긴 증가하는 부분 수열 4

<문제 링크>

 

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

14002번: 가장 긴 증가하는 부분 수열 4

 

---

<풀이>

 

수열이 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 문제이며, 시리즈 중 4번째 문제이다.

전과 달라진 점은 둘째 줄에 부분 수열을 출력해야 하며, 첫째 줄은 기존과 마찬가지로 부분 수열의 길이를 출력하면 된다.

동적 프로그래밍으로 풀이 가능하기 때문에 dp를 선언 한 다음에 A의 순서대로 2차원 배열 arr를 만들어준다.

# 1: dp를 채우기 위해 모든 경우에 대해 for문이 작동하며, 새로운 큰 값을 발견하고 길이가 작을 경우에 기존(arr[j])에 나 자신 A[i]를 더해준다.

# 2: 가장 길이가 큰 dp를 구하고 그 dp의 index 값을 arr에서 뽑아내 출력

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    dp = [0] * N
    arr = [[x] for x in A]

    # 1
    for i in range(N):
        for j in range(i):
            if A[i] > A[j] and dp[i] < dp[j]:
                arr[i] = arr[j] + [A[i]]
                dp[i] = dp[j]
        dp[i] += 1

    # 2
    max_count = max(dp)
    print(max_count)
    print(*arr[dp.index(max_count)])