[2023-05-30] 2491 수열 (Kotlin)

많이 아파서 포스팅을 못했습니다.

 

설상가상으로 운영중인 앱이 터져버려 고치는데 시간을 많이 쏟았고,

 

동생 군대 배웅해주려 지방까지 갔다오는 둥 많이 바빴습니다.

 

 

 

문제 링크: https://www.acmicpc.net/problem/2491

2491번: 수열

 

2중 반복으로 풀었는데, 계속 시간초과가 떠서 고생했습니다.

 

1시간 고민하고, dp로 접근해야겠다 생각했지만,

결국 풀지 못하고 다른 분의 풀이를 참고하였습니다.

 

 

package fiftyeighth
import java.io.*
fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val input = br.readLine().split(' ').map{it.toInt()}
    val dp = Array(n){0}
    val dp1 = Array(n){0}
    for (index in 1 until input.size){
        if (input[index - 1] <= input[index]){
            dp[index] = Math.max(dp[index], dp[index - 1] + 1)
        }
        if (input[index - 1] >= input[index]){
            dp1[index] = Math.max(dp1[index], dp1[index - 1] + 1)
        }
    }
    var max = 0
    for (index in dp.indices){
        max = Math.max(max, Math.max(dp[index], dp1[index]))
    }
    println(max + 1)
}