<백준> LCS(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/LCS

[백준]

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

제출 결과

 

개념을 잘 모를 때는 접근조차 힘들었지만 개념을 이해하고 나니까 매우 쉬운 문제였다.

다이나믹 프로그래밍을 이용해서 했다.

다이나믹 프로그래밍을 이용하지 않았다면 시간초과가 될 게 눈이 아른아른 보였기 때문이다.

 

한바퀴를 돌면서 값을 갱신시키는 방식이었는데 현재 인덱스에서 문자열의 값이 같은지 보고 이에 맞춰 코드를 수행하도록 짰다.

같을 때는 이전까지의 값에서 1을 더해줬다.

다를 때는 지금까지 오는 2가지 루트에서 큰 값을 저장했다.

현재 문제는 최장 공통 부분수열이라 중간에 다른 문자가 있어도 가장 긴 부분수열을 찾아 연결될 수 있어야하기 때문이다.

 

인덱스는 0에 해당하는 값을 비워놓기 위해 문자열의 인덱스에 다 1씩 더했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

val dp: Array<Array<Int>> = Array(1001) { Array(1001) { 0 } }
fun main() = with(System.`in`.bufferedReader()) {
    val s1 = readln()
    val s2 = readln()
    var lcs = 0

    for (i in s2.indices) {
        for (j in s1.indices) {
            dp[i + 1][j + 1] =
                if (s1[j] == s2[i]) {
                    dp[i][j] + 1
                } else {
                    maxOf(dp[i][j + 1], dp[i + 1][j])
                }
            lcs = maxOf(lcs, dp[i + 1][j + 1])
        }
    }

    println(lcs)
}

 

개념을 이해하기 쉽게 설명해준

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

감사합니다..!