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

문제

---

생각하기

---

• 문자열 문제이다.
  

• 메모이제이션을 활용하지 않으면 해결하기 힘들다.

  • 처음에 HashSet을 써서 완탐방식으로 풀었는데 당연히 실패...

• 메모이제이션의 2차원배열을 통해서 문제를 해결한다.

  • str과 str2를 하나씩 분해하면서 2차원 배열로 문자 하나씩 탐색해나간다.

동작

    for (i in 1 .. len1) {
        for (j in 1 .. len2) {
            if (str[i - 1] == str2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1
                ans = Math.max(ans, arr[i][j])
            }
        }
    }

str과 str2를 하나씩 분해해서 같은 문자가 올 경우 이전의 값을 그대로 들고 와서 +1을 한 결과를 지속적으로 memo에 저장하면서 최댓값을 갱신해나가면 정답을 찾을 수 있다.

코드

---

Kotlin

import java.io.*

// input
private lateinit var br: BufferedReader

// variables
private var str = ""
private var str2 = ""


fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()
    var ans = 0
    var len1 = str.length
    var len2 = str2.length
    var arr = Array(len1 + 1) { IntArray(len2 + 1) }

    for (i in 1 .. len1) {
        for (j in 1 .. len2) {
            if (str[i - 1] == str2[j - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1
                ans = Math.max(ans, arr[i][j])
            }
        }
    }

    sb.append(ans)
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun input() {
    str = br.readLine()
    str2 = br.readLine()
} // End of input