15482번: 한글 LCS

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

 

언어 : Kotlin

 

문제 설명 :

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

예를 들어, "최백준"과 "백준온라인"의 LCS는 "백준"이고, "스타트링크"와 "스트라토캐스터"의 LCS는 "스트"이다.

 

입력 :

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 최대 1000글자이고, 유니코드 U+AC00(가)부터 U+D7A3(힣)까지로만 이루어져 있으며, UTF-8로 인코딩 되어 있다.

 

출력 :

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
최백준 백준온라인	2
스타트링크 스트라토캐스터	2
선데이코딩 딩코이데선	1
가나다라가나다라 가다나가다라	5

 

풀이 : 

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

9251번: LCS와 비슷하다고 생각은 했는데 풀이법도 완전히 같았다.

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


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    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()
}