[백준] 9251번: LCS

kldaji·2021년 10월 25일
0

백준문제풀이

목록 보기
17/35
post-custom-banner

문제

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

풀이

  • 메모이제이션
  • LCS
import kotlin.math.max

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val word1 = br.readLine().toString()
    val word2 = br.readLine().toString()
    val dp = Array(word1.length + 1) { Array(word2.length + 1) { 0 } }
    for (i in word1.indices) {
        for (j in word2.indices) {
            if (word1[i] == word2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1
            } else {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
            }
        }
    }
    bw.write("${dp[word1.length ][word2.length]}")
    bw.close()
    br.close()
}

더 좋은 풀이 있으면 댓글 달아주세요!!!

profile
다양한 관점에서 다양한 방법으로 문제 해결을 지향하는 안드로이드 개발자 입니다.
post-custom-banner

0개의 댓글