9251번: LCS

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

9251번: LCS

언어 : Kotlin

 

문제 설명 :

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

• 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
• 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

제한 사항 :

• 시간 제한 : 0.1초
• 메모리 제한 : 256MB
• Java 8: 0.4 초
  Python 3: 2 초
  PyPy3: 2 초
  Java 8 (OpenJDK): 0.4 초
  Java 11: 0.4 초
  Kotlin (JVM): 0.4 초
  Java 15: 0.4 초

 

입출력 예 :

입력	출력
ACAYKP CAPCAK	4

다른 사람의 풀이(23.09.18 수정) : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import kotlin.math.max

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

    val n = readLine()
    val m = readLine()
    val dp = Array(n.length + 1) { Array(m.length + 1) { 0 } }

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

    bw.write("${dp[n.length][m.length]}")
    bw.flush()
    bw.close()
}

 

자세한 풀이: https://velog.io/@noion0511/PythonKotlin-%EB%B0%B1%EC%A4%80-9251%EB%B2%88-LCS

[Python/Kotlin] 백준 9251번 : LCS

 

23-09-18. indexoutofbounds 오류가 떠서 수정했다.