[백준/코틀린] 9251번: LCS

링크

9251번: LCS

풀이

dp[i][j]: 첫 번째 문자열(A)의 i번째 문자와 두 번째 문자열(B)의 j번째 문자까지의 LCS 길이

출처: Wikipedia: Longest common subsequence

만약 A의 i번째 문자와 B의 j번째 문자가 같다면,
이는 A의 i-1번째 문자와 B의 j-1번째 문자까지의 LCS에 해당 문자를 추가한 것과 같습니다.
dp[i][j] = dp[i-1][j-1] + 1

A의 i번째 문자와 B의 j번째 문자가 다르다면,
두 문자를 동시에 사용하는 공통 부분 수열은 만들 수 없으므로,
A에서 문자를 하나 제외하거나 B에서 문자를 하나 제외한 경우를 고려합니다.

즉, A의 i-1번째 문자와 B의 j번째 문자까지의 LCS,
또는 A의 i번째 문자와 B의 j-1번째 문자까지의 LCS 중 더 긴 쪽을 선택합니다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

코드

fun main() {
    val a = readln()
    val n = a.length
    val b = readln()
    val m = b.length
    val dp = Array(n + 1) { IntArray(m + 1) }

    for (i in 1..n) {
        for (j in 1..m) {
            dp[i][j] = if (a[i - 1] == b[j - 1]) dp[i - 1][j - 1] + 1
            else maxOf(dp[i - 1][j], dp[i][j - 1])
        }
    }

    println(dp[n][m])
}