[백준] 9251번 LCS in Kotlin

📜 문제

문제 링크

💡 풀이

다이나믹 프로그래밍으로, 부분 결과를 이차원 배열 lcs에 저장했다.

입력받은 두 문자열 중 먼저 입력받은 것을 S1, 두번째로 입력받은 것을 S2라고 했을 때
lcs[i][j]를 S1를 i번째 문자까지 읽은 부분 문자열과 S2를 j번째 문자까지 읽은 부분문자열의 LCS 길이로 두었다.
예를 들어, S1 = ACAYKP, S2 = CAPCAK일 때
lcs[6][3]는 "ACAYKP"와 "CAP"의 LCS의 길이를 의미하며,
이때 LCS는 "CAP"로 lcs[6][3] = 3이다.

이차원 배열 lcs는 다음과 같은 규칙으로 채웠다.

S[n]을 문자열의 n번째 문자라고 하면,
1. S1[i]와 S2[j]가 같으면 lcs[i][j] = lcs[i - 1][j - 1] + 1
2. S1[i]와 S2[j]가 다르면 lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])

규칙에 대한 설명은 앞에서와 같이 S1 = ACAYKP, S2 = CAPCAK 예시로 설명하려고 한다.

• 먼저, 첫번째 규칙의 경우 i = 5, j = 3일 때 "ACAYKP"와 "CAP"의 LCS의 길이를 구하는 경우를 생각해보자.
  현재 비교하고자 하는 S1[i]와 S2[j]가 'P'로 같기 때문에 이전까지 구한 공통 부분 수열에 P를 추가하게 된다. 즉,"ACAYKP"와 "CAP"의 LCS는 "ACAYK"와 "CA"의 LCS에 'P'를 붙인 것과 같다.
  따라서 lcs[5][3] = lcs[4][2] + 1이라고 볼 수 있고,
  일반화하여 lcs[i][j] = lcs[i - 1][j - 1] + 1이라는 식을 도출해낼 수 있다.

• 두번째 규칙의 경우 i = 5, j = 4일 때 "ACAYKP"와 "CAPC"의 LCS의 길이를 구하는 경우를 생각해보자.
  현재 비교하고자 하는 S1[i]와 S2[j]가 서로 다르기 때문에 i와 j를 넘어가지 않는 선에서 이전까지 구한 공통 부분 수열 중 가장 긴 수열과 같게 된다. 즉, "ACAYKP"와 "CAP"의 LCS와 "ACAYK"와 "CAPC"의 LCS 중 긴 것과 같다.
  따라서 lcs[5][4] = max(lcs[4][4], lcs[5][3])이라고 볼 수 있고,
  일반화하여 lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])이라는 식을 도출했다.

이렇게 다이나믹 프로그래밍을 이용해서 문제를 풀면 S1의 길이 N, S2의 길이 M이라고 할 때 O(NM)만에 문제를 풀 수 있다.

⌨️ 코드

fun main() = with (System.`in`.bufferedReader()) {
        val s1 = readLine()
        val s2 = readLine()
        val s1Count = s1.length
        val s2Count = s2.length

        val lcs = Array(s1Count + 1) { IntArray(s2Count + 1) }

        for (i in 1..s1Count) {
            for (j in 1..s2Count) {
                if (s1[i - 1] == s2[j - 1]) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1])
                }
            }
        }

        println(lcs[s1Count][s2Count])
}

😄 느낀 점

사실 dp table을 어떻게 세워야할지 모르겠어서 답안을 보고나서야 정답을 알아낼 수 있었다..
dp는 아이디어를 떠올리기가 힘들어서 항상 나에게 두려움을 주는 문제였는데, 오늘부터 무서워하지 않기로 했다. 끝까지 고민해보고, 당분간 dp만큼은 정답을 확인하고나서 내 지식으로 만들어보는 연습을 하려고 한다. 화이팅!!!