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

문제

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

 

문제 풀이

 이전에 다루었던 11053 가장 긴 증가하는 부분 수열의 풀이에서 각 원소들만 추가해주면 된다. 이는 메모이제이션을 통해 수열의 값의 크기에 따라 앞의 수 중 작은수가 얼만큼 있는지 확인할 수 있기 때문이다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    nums = list(map(int, stdin.readline().split()))
    # 자기자신은 포함하므로 1로 초기화
    answer = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                answer[i] = max(answer[i], answer[j] + 1)

    max_len = max(answer)
    print(max_len)
    # 추가 된 부분
    ret = []
    for i, length in enumerate(answer[::-1]):
        if length == max_len:
            ret.append(nums[n - i - 1])
            max_len -= 1

    print(*ret[::-1])

 증가하는 최대 수열이 되는 원소 부터, 길이를 1씩 감소 시켜가며 증가하는 순열의 값을 찾을 수 있다. 뒤에서 부터 리스트에 값을 기록하게 되므로 출력 할때는 반전시켜주어야 한다.