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

문제

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하라.

 

입력

첫째 줄에 수열의 크기 N이 주어진다.

둘째 줄에는 N개의 수를 갖는 수열이 주어진다.

 

출력

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

---

접근

가장 긴 증가하는 부분수열을 구하는 것을 LIS 알고리즘이라 하고 완전 탐색, 동적 계획법, 이진 탐색의 방법이 있다. 이 문제에서는 동적 계획법으로 접근을 했다.

 

{10 20 10 30 20 50}이라는 수열이 있을 때 30까지의 증가하는 부분수열을 구해보자. 

이전에 20의 증가하는 부분수열의 길이는 2이다. 

- 10과 30을 비교했을 때 30이 더 크다. 

- 이제 증가하는 부분수열은 10+30로 길이는 2이다. 원래 10만 있었을 때 길이인 1보다 크기 때문에 2로 갱신한다.

- 그 다음 20이랑 비교했을 때도 30이 더 크다. 

- 20까지의 증가하는 부분 수열 길이는 2이고 여기에 30을 더하게 되어 3이 더 긴 길이이기 때문에 3으로 갱신한다.

- 10이랑 비교했을 때는 30이 더 크긴하지만 10의 증가하는 부분 수열의 길이는 1이고 여기에 +1 한다 해도 최대길이가 갱신되지 않는다.

- 최종적으로 길이가 3인 것을 확인할 수 있다.

 

이처럼 범위를 넓혀가면서 가장 끝에 있는 수를 포함하여 앞의 수와 비교하고 증가하는 부분수열의 길이를 구한다.

 

구현

- 초기에 메모제이션을 할 리스트인 cache에 1로 초기화한다.

- 이후 LIS가 되는 수열도 출력해야 하기 때문에 lis를 선언하고 해당 자리에 맞는 수를 넣는다.

N = int(input())
numbers = list(map(int, input().split()))
cache = [1 for _ in range(N)]
lis = [[number] for number in numbers]

 

- 이중 for문으로 LIS를 찾는다.

- 접근에서 말했던 것을 아래처럼 구현하였다.

- 인덱스 i는 가장 끝에 있는 수를 의미하고 이전의 수보다 클 때 반드시 포함하여 LIS를 구한다.

- cache에는 i의 수를 포함했을 때 LIS의 길이가 저장되어있다.

for i in range(N):
    for j in range(i):
        if numbers[j] < numbers[i]:
            if cache[i] < cache[j] + 1:
                lis[i] = lis[j] + [numbers[i]]
                cache[i] = cache[j] + 1

 

- 이제 LIS의 길이를 담은 cache에서 가장 큰 수를 찾는다.

- 동시에 인덱스도 찾아서 출력조건대로 출력할 수 있도록 한다.

max_value = -1
max_idx = -1
for i in range(N):
    if max_value < cache[i]:
        max_value = cache[i]
        max_idx = i

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
numbers = list(map(int, input().split()))
cache = [1 for _ in range(N)]
lis = [[number] for number in numbers]

for i in range(N):
    for j in range(i):
        if numbers[j] < numbers[i]:
            if cache[i] < cache[j] + 1:
                lis[i] = lis[j] + [numbers[i]]
                cache[i] = cache[j] + 1

max_value = -1
max_idx = -1
for i in range(N):
    if max_value < cache[i]:
        max_value = cache[i]
        max_idx = i

print(max_value)
print(*lis[max_idx])