[백준 | 골드4] 14002번: 가장 긴 증가하는 부분 수열 4

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

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

 

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4
10 20 30 50

 

 

문제풀이

증가수열 문제과 같은 방법으로 최대 증가수열의 길이를 구하고

그 구한 길이를 가지고 dy에서 긴값을 찾으면 길이를 -1 해주면서 최대 길이의 인덱스를 가지고 값을 찾는다.

import sys
input = sys.stdin.readline

n = int(input())
data_list = list(map(int, input().split()))
data_list.insert(0, 0)          #1부터 시작하기 위해서 맨 앞에 0 삽입
result_num = []
dy = [0] * (n + 1)
dy[1] = 1                       #인덱스 1에는 앞에 붙일 숫자 없음


def solutuon(n) :
    result_max = 0
    

    if n == 1 :
        print(1)
        print(data_list[1])
        return

    for i in range(2, n+1) :
        max_len = 0

        #i-1부터 0까지 data_list[i]값 보다 작으면서 최대 길이가 긴 경우
        #그 긴 길이에 +1 해서 증가 수열을 구함
        for j in range(i-1, 0, -1):
            if data_list[j] < data_list[i] and dy[j] > max_len :        #[i]보다 [j]는 무조건 작은 수
                max_len = dy[j]                                         #최대 길이값 찾음
        dy[i] = max_len + 1                                             #i-1번째부터 최대 길이 찾은 값으로부터 +1 한다

        
        #만들어둔 dy값을 이용해서 제일 긴 증가수열 찾음
        if dy[i] > result_max : 
            result_max = dy[i]
    
    order = result_max              #dy의 최대 길이 저장

    for i in range(n, 0, -1) :      #dy리스트를 -1하면서 <--- 방향으로 찾음
        if dy[i] == order :         #최대 길이를 찾았늘때
            result_num.append(data_list[i])         #그 인덱스가 최대 길이 만든 값
            order -= 1              #-1해줘서 다음 작은 최대 길이 찾기
    
    result_num.reverse()    

    print(result_max)
    print(" ".join(map(str, result_num)))

solutuon(n)