백준 9251번
https://www.acmicpc.net/problem/9251

문제

---

생각하기

---

• LCS 기초 문제이다.

  • 메모이제이션 DP를 활용해서 해결했다.

동작

결과

코드

---

Kotlin

재귀

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()