백준 9251번
https://www.acmicpc.net/problem/9251
LCS 기초 문제이다.
재귀
import java.io.*
// input
private lateinit var br: BufferedReader
// variables
private var str1 = ""
private var str2 = ""
private lateinit var memo: Array<IntArray>
fun main() {
br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
input()
bw.write(solve())
bw.close()
} // End of main()
private fun solve(): String {
val sb = StringBuilder()
sb.append(LCS(str1.length, str2.length))
return sb.toString()
} // End of solve()
private fun LCS(n: Int, m: Int): Int {
if (m == 0 || n == 0) {
return 0
}
if (memo[n][m] != -1) {
return memo[n][m]
}
if (str1[n - 1] == str2[m - 1]) {
memo[n][m] = 1 + LCS(n - 1, m - 1)
} else {
memo[n][m] = LCS(n - 1, m).coerceAtLeast(LCS(n, m - 1))
}
return memo[n][m]
} // End of LCS()
private fun input() {
str1 = br.readLine()
str2 = br.readLine()
memo = Array(str1.length + 1) { IntArray(str2.length + 1) { -1 } }
} // End of input()
반복문
import java.util.*
import java.io.*
// input
private lateinit var br: BufferedReader
// variables
private var str1 = ""
private var str2 = ""
private var N = 0
private var M = 0
private lateinit var memo: Array<IntArray>
fun main() {
br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
input()
bw.write(solve())
bw.close()
} // End of main()
private fun solve(): String {
val sb = StringBuilder()
for (i in 1..N) {
for (j in 1..M) {
if (str1[i - 1] == str2[j - 1]) {
// 현재 문자가 같을 경우
memo[i][j] = memo[i - 1][j - 1] + 1
} else {
memo[i][j] = memo[i - 1][j].coerceAtLeast(memo[i][j - 1])
}
}
}
sb.append(memo[N][M])
return sb.toString()
} // End of solve()
private fun input() {
str1 = br.readLine()
str2 = br.readLine()
N = str1.length
M = str2.length
memo = Array(N + 1) { IntArray(M + 1) }
} // End of input()