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

문제 링크

하아아아아 억울해 왜 이 생각을 못해냈을까 ...

증가하다가 감소하게되는 가장 긴 수열을 알아내면 되는 것이기 때문에
증가하는 부분수열과
감소하는 부분수열을 각각 구해서
그 두개를 더한 값의 최대값을 구하면 된다.

이 때 주의할 점이 두 가지 있는데
1. 두 개를 더하면 더해지는 그 경곗값이 두 번 더해지는 것이기 때문에 1을 빼줘야한다.
2. 감소하는 부분수열 값은 기존 수열의 역의 증가하는 부분수열의 역 이다...

• 예를 들어, [1, 5, 2, 1, 4, 3, 4, 5, 2, 1] 수열의 감소하는 부분수열은
  • 기존 수열에서 reversed한 [1, 2, 5, 4, 3, 4, 1, 2, 5, 1] 수열의
  • 증가하는 부분수열 [1, 2, 3, 3, 3, 4, 1, 2, 5, 1]를
  • reversed() 한 [1, 5, 2, 1, 4, 3, 3, 3, 2, 1] 이다.

최종 풀이

import Foundation

let N = Int(readLine()!)!
let nArray = readLine()!.split(separator: " ").map { Int(String($0))!}
let lArray = Array(nArray.reversed())

var r_dp = Array(repeating: 1, count: N)
var l_dp = Array(repeating: 1, count: N)
var dp = Array(repeating: 1, count: N)

for i in 1..<N {
    for j in 0..<i {
        if nArray[j] < nArray[i] {
            r_dp[i] = max(r_dp[i], r_dp[j] + 1)
        }
    }
}

for i in 1..<N {
    for j in 0..<i {
        if lArray[j] < lArray[i] {
            l_dp[i] = max(l_dp[i], l_dp[j] + 1)
        }
    }
}

l_dp = Array(l_dp.reversed())
for i in 0..<r_dp.count {
    dp[i] = r_dp[i] + l_dp[i]
}

print(dp.max()! - 1)