[백준 11054] 가장 긴 바이토닉 부분 수열

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

✍️ 첫번째 접근

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족하는 부분 바이토닉 수열이면서 그 중 가장 긴 수열을 구하면 된다.
LIS를 구하는 방식 중 2중 for문을 사용하는 방법과 이분탐색을 통해 구하는 방법이 있는데 첫번째 방법은 시간 복잡도가 O(n^2)이다. 따라서, 시간초과를 피하기 위해 시간 복잡도가 O(logn)인 두번째 방법을 택하였다.
입력으로 받은 수열에 대해서,

• 앞->뒤 방향으로 LIS 구하기(why? 정방향에서 봤을 때 Sk를 기준으로 증가하므로)
• 뒤->앞 방향으로 LIS 구하기(why? 역방향에서 봤을 때 Sk를 기준으로 증가하므로)

먼저 위와 같은 논리를 계획하였다.

• 1번) 앞->뒤 방향으로 LIS구하고 LIS에 값이 들어가는 마지막 인덱스로부터 뒤->앞 방향으로 LIS를 구해 이 둘의 LIS합이 곧 부분 바이토닉 수열의 합이다.
• 2번) 뒤->앞 방향으로 LIS구하고 LIS에 값이 들어가는 마지막 인덱스로부터 앞->뒤 방향으로 LIS를 구해 이 둘의 LIS합이 곧 부분 바이토닉 수열의 합이다.

둘 중 큰 값이 길이가 가장 긴 바이토닉 부분 수열의 길이라고 판단하여 구현하였지만 틀렸다는 결과를 받았다.

import Foundation

func binary_search(_ LIS: [Int], _ left: Int, _ right: Int, _ target: Int) -> Int {
    var left = left
    var right = right
    var mid = 0
    while left < right {
        mid = (left+right)/2
        if LIS[mid] < target {
            left = mid + 1
        }
        else {
            right = mid
        }
    }
    return right
}

func findLIS(_ arr: [Int]) -> (Int,Int) {
    var LIS = Array(repeating: 0, count: arr.count+1)
    var i = 1, j = 0
    var maxI = 0
    LIS[0] = arr[0]
    while i < arr.count {
        if arr[i-1] == arr[i] {
            maxI = i
        }
        if LIS[j] < arr[i] {
            j += 1
            LIS[j] = arr[i]
            maxI = i
        }
        else {
            let index = binary_search(LIS, 0, j, arr[i])
            LIS[index] = arr[i]
        }
        i += 1
    }
    return (j+1,maxI)
}

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var answer1 = 0, answer2 = 0
// 앞에서부터 시작하는 LIS -> 뒤에서부터 시작하는 LIS
var (a,b)  = findLIS(arr)
answer1 += a
if b+1 < arr.count {
    (a,b) = findLIS(Array(arr[b+1..<arr.endIndex].reversed()))
    answer1 += a
}
// 뒤에서부터 시작하는 LIS -> 앞에서부터 시작하는 LIS
(a,b) = findLIS(arr.reversed())
answer2 += a
if b < arr.count-1 {
    (a,b) = findLIS(Array(arr[0..<arr.count-b-1]))
    answer2 += a
}
print(max(answer1,answer2))

✍️ 두번째 접근

아래의 반례를 찾아 내 논리가 부족하다는 것을 깨달았다.

10
10 1 3 5 7 6 3 2 1 10
ans: 8

내 논리대로라면, 1번)의 결과는 1 3 5 7 10이고 2번)의 결과는 1 2 3 6 7 10이므로 정답이 6이라는 틀린 판단을 하게 된다.
따라서, 입력받은 각각의 인덱스에 대해서 정방향 LIS와 역방향 LIS를 구하는 방식을 선택하였다.
위의 반례를 들어서 설명하면,
i=4라고 했을 때 10 1 3 5 7의 정방향 LIS와 7 6 3 2 1 10의 역방향 LIS를 구한다. 이 둘의 길이를 더하고 7이 중복되므로 1을 뺀다.
i는 0부터 9까지 위와 같은 작업을 진행해 나온 값 중에 가장 큰 값을 출력하여 해결할 수 있었다.

import Foundation

func binary_search(_ LIS: [Int], _ left: Int, _ right: Int, _ target: Int) -> Int {
    var left = left
    var right = right
    var mid = 0
    while left < right {
        mid = (left+right)/2
        if LIS[mid] < target {
            left = mid + 1
        }
        else {
            right = mid
        }
    }
    return right
}

func findLIS(_ arr: [Int]) -> Int {
    var LIS = Array(repeating: 0, count: arr.count+1)
    var i = 1, j = 0
    LIS[0] = arr[0]
    while i < arr.count {
        if LIS[j] < arr[i] {
            j += 1
            LIS[j] = arr[i]
        }
        else {
            let index = binary_search(LIS, 0, j, arr[i])
            LIS[index] = arr[i]
        }
        i += 1
    }
    return j+1
}

let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var answer: [Int] = []
for i in 0..<arr.count-1 {
    let forward = findLIS(Array(arr[0...i]))    // 0번째부터 i번째까지의 LIS
    let backward = findLIS(Array(arr[i...arr.count-1]).reversed())    // i번째부터 마지막까지의 Longest Decreasing Subsequence를 구해야하므로 마지막부터 i번째까지에서 LIS를 구함.
    answer.append(forward+backward-1)
}
print(answer.max() ?? 1)