글 읽기 - 어떤 TC를 충족하지 못했을까요..

pk920207 3년 전 0

수열을 순차적으로 돌면서

자기보다 작은 수열 원소의 최종 길이가, 자기보다 큰 경우 +1 하여 세팅하는 방식으로 풀었습니다. (아마 이게 전형적인 방식인 듯)

println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(10, 20, 10, 30, 20, 50)) == 4)
println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(19, 22, 23, 20, 10, 30, 25)) == 4)
println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(1)) == 1)
println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(3, 2, 1)) == 1)
println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(1,2,3,4,5,6,7,8)) == 8)
println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(1,2)) == 2)
println(`가장 긴 증가하는 부분 수열`().solution(intArrayOf(50,10,20,10,40)) == 3)

테스트해본 TC들은 위와 같은데.. 제출시에 실패하네요. 혹시 제가 캐치하지 못한 TC가 있을까요 ㅜㅜ

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

fun main(args: Array<String>) {
    try {
        val fn = `가장 긴 증가하는 부분 수열`()
        val br = BufferedReader(InputStreamReader(System.`in`))
        val count = br.readLine().toInt()
        val sequence = br.readLine().split(" ").stream()
            .mapToInt { it.toInt() }
            .toArray()
        println(fn.solution(sequence))
    } catch (e: IOException) {/* */}
}

class `가장 긴 증가하는 부분 수열` {
    fun solution(sequence: IntArray): Int {
        val dp = IntArray(sequence.size) { 1 }

        var max = 1
        for (i in 1 until sequence.size) {
            var latest = 0

            for (j in i-1 downTo 0) {
                if (!(sequence[j] < sequence[i] && sequence[j] > latest)) {
                    break
                }

                if (dp[j] >= dp[i]) {
                    dp[i] = dp[j] + 1
                    latest = sequence[j]
                }
            }

            max = max(dp[i], max)
        }

        return max
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 TC를 충족하지 못했을까요..

pk920207 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말