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

요구능력 : DP에 대한 이해

 

코드설명 : 

 

바이토닉 부분수열을 오해하고 문제를 풀었다.

증가하다가 가운데가 가장크고 점점 작아지는 수가 나오는줄알고 처음에는 증가하는 부분수열 + 인덱스저장 + 감소하는 부분수열로 풀었는데, 생각보다 간단하게 풀리는 문제였다.

이론적인 부분은 https://st-lab.tistory.com/136 엄청 잘 정리해 놓으셨다.

 

우선 가장 긴 증가하는 부분수열 dp를 구하고,

가장 긴 감소하는 부분수열 dp를 구해준다.

 

그리고 두 dp의 각 인덱스를 합쳐주고 1씩 빼주면 그게 두 수열을 합친것이다.

그래서 점점 작아지는 부분과 점점 커지는 부분이 합쳐져서 바이토닉 수열이된다.

 

내가 이해가 안갔던 부분을 위주로 설명하자면,

두 개를 합친다고 어떻게 하나의 바이토닉 수열이 되는가?

두개의 인덱스를 각각합치고 한개의 인덱스를 임의로 정해서 기준으로 양쪽을 보면 이해가 쉽다.

예를 들면 저렇게 봤을 때 왼쪽은 오름차순 오른쪽은 내림차순으로 오는수가 임의로 정한 인덱스에서 만나서 하나의 수열을 이룬다.

 

1씩 빼주는 이유는?

중복되는 수 때문이다.

위에서 말했듯 임의의 인덱스를 정해서 왼쪽오른쪽을 바라보면 된다.

예를 들어서 1 2 3 2 1이 있을 때 3을 두고 보면

1 2 3

3 2 1

이렇게 가장긴 증가하는 부분수열과 가장 긴 감소하는 부분수열이 보인다.

여기서 3은 2번 중복되기 때문에 1을 빼줘야 자연스러운 바이토닉 수열인 1 2 3 2 1의 개수가 완성된다.

 

후기 : 꽤나 신박한 문제이다.. 상상도 못한 풀이법이었다.

유연한 사고가 필요한 문제..

let a = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp_1 = Array(repeating: 1, count: 1001)
var dp_2 = Array(repeating: 1, count: 1001)
var result: [Int] = []

for i in stride(from: 1, through: a, by: 1){
    for j in 1...i{
        if arr[i - 1] > arr[j - 1]{
            dp_1[i] = max(dp_1[i], dp_1[j] + 1)
        }
    }
}


for i in stride(from: a, through: 1, by: -1){
    for j in stride(from: a, through: i, by: -1){
        if arr[i - 1] > arr[j - 1]{
            dp_2[i] = max(dp_2[i], dp_2[j] + 1)
        }
    }
}
for i in 1...a{
    result.append(dp_1[i] + dp_2[i])
}
print(result.max()! - 1)