백준 5582번 공통 부분 문자열 코틀린

lcs를 이용한 dp 문제이다.

두 문자의 길이에 따라 각각 i행과 j열로 이루어진 표를 만들고

i행의 문자와 j열의 문자가 같으면 값을 표시하면 된다.

현재 값이 같고(i, j) 대각선 위의(i-1, j-1) 값이 같은 경우면 문자가 연속 된 경우임으로 해당값(i-1, j-1)에 +1을 해주면 된다. (표를 그려보면 알 수 있다.)

 

코틀린으로 풀때 자꾸 메모리 초과가 나와서 실패 했는데..

Array(row) {Array{column} {0}} 으로 초기화 할 경우 0으로 초기화 하는 과정에서 메모리 문제로 실패하게 된다ㅠ

 

fun main() {
    val word1 = readLine()!!
    val word2 = readLine()!!

    val row = word1.length + 1
    val column = word2.length + 1

    val dp = Array(row) { IntArray(column) }
    var max = 0

    for (i in 1 until row) {
        for (j in 1 until column) {
            if (word1[i - 1] == word2[j - 1]) {
                if (i -1 == 0 || j - 1 == 0) {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                }
                if (dp[i][j]>max) {
                    max = dp[i][j]
                }
            }
        }
    }
    println(max)
}