Algorithm & Data Structure
2022. 8. 15.
백준 - 11045번(DP,LIS 응용)
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 바이 토닉 부분 수열 문제다. 가장 긴 증가하는 부분 수열에서 감소가 추가된 것이다. 따라서 가장 긴 증가하는 부분 수열, 즉 LIS를 찾아준 다음에 뒤에서부터 다시 LIS를 찾아준다. 이렇게 나온 두개의 inc 배열과 dec 배열을 합친 다음에 1을 빼준다. 왜 1을 빼주냐면 가장 큰 값 즉 증감이 변하는 부분의 값이 두 번 들어갔기 때문이다. 합쳐서 나온 리스트에서 가장 큰 값을 찾아주면 그게 정답이다...