백준 9251번 with Kotlin

LCS

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

38775

16009

11724

40.549%

문제

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

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

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

예제 입력 1 복사

ACAYKP CAPCAK

예제 출력 1 복사

4

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: qpwoeiruty

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Integer.max
 
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main()=with(br){
    val str1 = readLine()
    val str2 = readLine()
    val lcs = Array(str1.length+1,{IntArray(str2.length+1,{0})})
 
    for(i in 1 until str1.length+1){
        for(j in 1 until str2.length+1){
            if(str1[i-1]==str2[j-1]){
                lcs[i][j] = lcs[i-1][j-1]+1
            }
            else{
                lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
            }
        }
    }
    bw.write("${lcs[str1.length][str2.length]}")
    bw.flush()
    bw.close()
}

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

https://happylsm76.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251%EB%B2%88LCS-with-Python