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

문제

 

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

11054번: 가장 긴 바이토닉 부분 수열

 

 

풀이

 

전깃줄문제에서 배웠던 LIS문제였다. 

 

우선, 나는 주어진 입력에서 각 원소별로 LIS 길이를 구해서 result에 넣어주었다.

해당 숫자까지 다시 반복문을 통해 오름차순의 길이를 구해주었다. max를 이용해 현재 값과 이전의 값의 1을 더한 값을 비교해주었다.

 

바로 1을 더한 값으로 바꿔주지 않은 이유는 단순하게 작은 숫자만 확인하는 것이 아니라 오름차순이기때문에 result[j] + 1의 값과 비교를 해야한다.

 

이렇게 LIS의 길이를 구해줬으면 반대로 돌려서 동일하게 구해준다.

 

그 후, 두 배열을 합해서 최대값을 출력하면 된다.

import Foundation

let n = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
let reversedNum = Array(numbers.reversed())
var result = Array(repeating: 1, count: n)
var second = Array(repeating: 0, count: n)
for i in 0..<n {
    for j in 0..<i {
        if numbers[j] < numbers[i] {
            result[i] = max(result[i],result[j] + 1)
        }
        if reversedNum[j] < reversedNum[i] {
            second[n - 1 - i] = max(second[n - 1 - i],second[n - 1 - j] + 1)
        }
    }
}
for i in 0..<n {
    result[i] += second[i]
}
print(result.max()!)

 

 

_____________________________________________________________________________________________________

 

 

시간초과가 나올 것 같아서 망설였지만 바로 해보길잘했다. 바로맞았음.