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

문제

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

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

풀이

가장 긴 증가하는 부분 수열을 구하는 방법으로는 DP($O(n^2)$), 이분탐색($O(nlogn)$) 등의 방법이 있지만,
N이 1,000이므로 DP를 사용해 $O(n^2)$으로도 풀이할 수 있습니다.

길이를 구하는 방법으로는 이전 포스팅에서 구한 방법으로 구할 수 있습니다.
https://dev-mandos.tistory.com/217

[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 (Swift)

현재 길이를 최대 길이의 값으로 설정하고
수열을 구하기 위해 DP로 사용한 배열을 끝에서 부터 조회를 하면서, 현재 길이와 같다면
입력받은 배열의 해당 인덱스에 해당하는 요소를 LIS 배열에 넣어줍시다.

그렇다면 LIS 배열 안에는 수열이 역순으로 들어가게 되므로,
역순으로 출력해주면 수열을 구할 수 있습니다.

소스코드

후기

LIS의 길이를 구하는 것은 이미 풀었기에 익숙하게 작성할 수 있었습니다.
LIS를 출력하기 위해, DP에 사용된 값을 다시 사용하는 방식으로 풀이했습니다.