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

1.문제 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

3. 출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

---

4. 포인트

1. 동적계획법을 떠올려야한다.
2. 문제를 쪼개어 가장 긴 부분수열을 조합하여 풀어야한다. 

1.  

4. 문제 풀이

[가장 긴 부분 수열 문제를 풀지 않았다면 이 문제를 먼저 푸는 것을 추천드립니다]

 

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

11053번: 가장 긴 증가하는 부분 수열

 

이미 가장 긴 부분 수열을 풀었음에도 바로 가장 긴 부분 수열 개념을 떠올리지 못했고 고민 끝에 두개의 가장 긴 증가하는 부분 수열을 생각해 낼 수 있었다.

바이토닉 수열을 봤을때 앞부분은 증가하고 뒷부분은 감소하는 것을 알  수 있다.

결국 앞부분은 가장 긴 증가하는 부분 수열로 뒷부분은 역순의 가장 긴 부분 수열로 구현할 수 있다.

이때 역순은 단순히 LIS를 뒤집은 것이 아닌 가장 뒤의 Index 부터 나아가는 것을 의미한다.

 

이렇게 구해낸 두 수열을 더 한값에서 -1 을 하면 결과를 얻을 수 있다.

-1 은 두 수열 모두 현재 Index에 있는 자기 자신을 포함하여 중복이 일어나기 때문이다.

 

 

 

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt()

    val arr = readLine().split(" ").map { it.toInt() }

    val dp = IntArray(N) { 0 }
    val lis = IntArray(N) { 1 }
    val reversedLis = IntArray(N) { 1 }

    for (i in 1 until N) {
        for (j in 0 until i) {
            if (arr[i] > arr[j]) {
                lis[i] = max(lis[i], lis[j] + 1)
            }
        }
    }

    for (i in N - 2 downTo 0) {
        for (j in N - 1 downTo i+1) {
            if (arr[i] > arr[j]) {
                reversedLis[i] = max(reversedLis[i], reversedLis[j] + 1)
            }
        }
    }

    var max = 0
    for (i in 0 until N) {
        if (max < reversedLis[i] + lis[i])
        max = reversedLis[i] + lis[i]
    }


    println(max -1 )

}