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

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

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

 

난이도 : 골드 4
태그 :  가장 긴 바이토닉 부분 수열

 

 

설명

가장 긴 증가한는 부분수열(LIS, Longest Increasing Subsequence),

가장 긴 감소하는 부분수열(LDS, Longest Decreasing Subsequence)과 비슷하게

가장 긴 증가했다가 줄어드는 부분 수열을 찾는 문제입니다.

 

첫 접근은

다이나믹 프로그래밍 배열 두개를 사용하여,

하나는 쭉 증가하다가, 다른 하나는 어느 순간부터 줄어들기 시작하는 상태를 저장하려 했으나...

말로도 설명하기 복잡한데 코드로 구현하려니까 더 복잡하더군요

 

이후 다른 접근법을 찾아보다가,

가장 긴 증가하는 부분수열을 양쪽으로 수행하여

한 지점을 기준으로 왼쪽 dp, 오른쪽 dp의 값을 더함으로써 접근하였습니다.

 

그림으로 표현하자면 다음과 같습니다

즉, 인덱스 별로 양 끝에서 증가하는 부분수열을 진행하면 된다는 것이죠.

처음에는 증가하는 부분수열, 지금 idx 이후로는 감소하는 부분수열을 하려 했는데,

그것보다 양 방향으로 증가하는 부분수열을 하는게 더 간단하더라고요.

 

 

소스코드

전체 소스코드

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

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val st = StringTokenizer(br.readLine(), " ")
    val arr = Array(n + 1) { 1 }
    val rightDP = Array(n + 1) { 1 }
    val leftDP = Array(n + 1) { 1 }

    for (i in 1..n) {
        arr[i] = st.nextToken().toInt()
    }

    for (i in 1..n) {
        for (j in 1 until i) {
            if (arr[i] > arr[j]) leftDP[i] = max(leftDP[i], leftDP[j] + 1)
        }
    }

    for (i in n downTo 1    ) {
        for (j in n downTo i + 1) {
            if (arr[i] > arr[j]) rightDP[i] = max(rightDP[i], rightDP[j] + 1)
        }
    }

    var max = 0

    for (i in 1..n) {
        max = max(max, rightDP[i] + leftDP[i])
    }
    println(max - 1)
}

 

전체 소스코드 입니다.

rightDP는 오른쪽 -> 왼쪽으로 진행하는 dp,

leftDP는 왼쪽 -> 오른쪽으로 진행하는 dp입니다.

 

이후, 입력으로 주어진 문자열을 차례로 돌며

양 배열의 최대값을 찾습니다.

 

양쪽 배열 모두 시작값이 1 이므로 중복되어,

답을 출력할때는 -1을 하여 출력합니다.

 

 

 

후기

양쪽으로 LIS를 진행한다는 아이디어를 잘 떠올리지 못해

생각보다 꽤 헤메였던 문제였습니다.