1958번: LCS 3

문제 출처 : https://www.acmicpc.net/problem/1958

1958번: LCS 3

언어 : Kotlin

 

문제 설명 :

문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.

이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.

 

입력 :

첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다.

 

출력 :

첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 LCS의 길이를 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

입출력 예 :

입력	출력
abcdefghijklmn bdefg efg	3

 

풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val s1 = readLine()
    val s2 = readLine()
    val s3 = readLine()
    val arr: Array<Array<IntArray>> = Array(s1.length + 1) { Array(s2.length + 1) { IntArray(s3.length + 1) { 0 } } }
    for (i in 1 until s1.length + 1) {
        for (j in 1 until s2.length + 1) {
            for (k in 1 until s3.length + 1) {
                if (s1[i - 1] == s2[j - 1] && s2[j - 1] == s3[k - 1])arr[i][j][k] = arr[i - 1][j - 1][k - 1] + 1
                else arr[i][j][k] = arr[i - 1][j][k].coerceAtLeast(arr[i][j - 1][k].coerceAtLeast(arr[i][j][k - 1]))
            }
        }
    }

    bw.write("${arr[s1.length][s2.length][s3.length]}")
    bw.flush()
    bw.close()
}