[백준] 9251. LCS (Kotlin)
2021. 9. 3. 14:30
문제 : https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
표로 나타내보면 더 쉽게 확인할 수 있다.
import java.util.*
import kotlin.math.max
var str1 =""
var str2 =""
lateinit var dp : Array<Array<Int>>
fun main() = with(Scanner(System.`in`)){
str1 = nextLine()
str2 = nextLine()
var max = 0
dp = Array(str2.length+1){Array(str1.length+1){0} }
for(i in str2.indices){
find(i)
}
for(i in 0 until str2.length+1){
for(j in 0 until str1.length+1){
// print("${dp[i][j]} ")
max = max(dp[i][j],max)
}
// println()
}
println(max)
}
fun find(twoIndex: Int){
for(oneIndex in str1.indices){
if(str1[oneIndex] == str2[twoIndex]){
dp[twoIndex+1][oneIndex+1] = dp[twoIndex][oneIndex]+1
}
else{
dp[twoIndex+1][oneIndex+1] = max(dp[twoIndex][oneIndex+1],dp[twoIndex+1][oneIndex])
}
}
}주석처리된 print부분을 사용하면 dp의 내부를 확인할 수 있다.
참고
반응형
