백준 11054번 가장 긴 바이토닉 부분 수열 - 스위프트(Swift) 풀이 + 그림 설명

1. 모든 i에 대해 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 LIS[i]를 구한다.
2. 모든 i에 대해 i번째 원소를 첫 번째로 하는 가장 긴 감소하는 부분 수열의 길이 reverseLIS[i]를 구한다.
3. i번째 원소를 기준으로 좌측은 증가하고 우측은 감소하는 가장 긴 바이토닉 부분 수열의 길이는 LIS[i] + reverseLIS[i] - 1이다.

---

1. 모든 i에 대해 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 LIS[i]를 구한다.

 일단 앞 부분에서는 증가를 해야 되기 때문에 LIS를 구해준다. DP를 사용해서 구하면 저절로 모든 i에 대해 i번째 원소를 마지막으로 하는 LIS 길이를 얻을 수 있다.

 

2. 모든 i에 대해 i번째 원소를 첫번째로 하는 가장 긴 감소하는 부분 수열의 길이 reverseLIS[i]를 구한다.

 뒷 부분은 감소해야 하는데, 감소는 증가 방향을 반대로 생각하면 된다. 맨 뒤(오른쪽)부터 왼쪽으로 가는 방향으로 LIS 배열을 한번 더 구해준다. 이렇게 방향을 반대로 뒤집어 주면 reverseLIS[i]의 의미는 i번째 원소를 처음으로 하는 가장 긴 감소하는 부분 수열의 길이가 된다.

 

3. i번째 원소를 기준으로 좌측은 증가하고 우측은 감소하는 가장 긴 바이토닉 부분 수열의 길이는 LIS[i] + reverseLIS[i] - 1이다.

 i번째 원소가 S_k가 되는 가장 긴 바이토닉 부분 수열의 길이는 i번째를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 + i번째를 첫 번째로 하는 가장 긴 감소하는 부분 수열의 길이 - 1 이 된다. 따라서 모든 i에 대해 탐색하면서 이 값이 가장 큰 것을 출력하면 된다.

 

 주어진 입출력 예시를 가지고 나타낸 과정이다. LIS로 앞에 5까지 증가하는 부분을 구하고, reverseLIS로 뒤에 5부터 감소하는 부분의 길이를 구한 것이다. 이때 5를 중복하여 셌으므로 1을 빼준다.

---

import Foundation

func solution() {
    let N = Int(readLine()!)!
    let arr = readLine()!.split(separator: " ").map{ Int(String($0))! }
    
    var LIS = Array(repeating: 1, count: N)
    var reverseLIS = Array(repeating: 1, count: N)
    
    for i in 0..<N {
        for j in 0..<i {
            if arr[j] < arr[i] {
                LIS[i] = max(LIS[i], LIS[j] + 1)
            }
            if arr[N-1-j] < arr[N-1-i] {
                reverseLIS[N-1-i] = max(reverseLIS[N-1-i], reverseLIS[N-1-j] + 1)
            }
        }
    }
    
    var result = 0
    
    for i in 0..<N {
        result = max(result, LIS[i] + reverseLIS[i] - 1)
    }
    
    print(result)
}

solution()