[백준][KOTLIN] 9251 LCS

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

9251번: LCS

풀이

1. 서로 입력된 두 단어를 전부 비교한다.

2. dp 에 비교하여 겹치는 단어의 개수를 저장한다.

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

3. 단어를 전부 비교한 표에서 규칙을 찾는다.

- 서로 같을 경우 현재 위치 기준으로 왼쪽 대각선 위 값보다 1큰 수를 저장 한다.

- 서로 다를 경우 현재 위치 기준으로 위쪽과 앞쪽 중 큰 수를 저장 한다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val letterA = br.readLine()
    val letterB = br.readLine()
    val dp = Array(letterA.length + 1) {
        IntArray(letterB.length + 1)
    }

    for (i in 1..letterA.length) {
        for (j in 1..letterB.length) {
            if (letterA[i - 1] == letterB[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            }
        }
    }

    println("${dp[letterA.length][letterB.length]}")
}

private fun max(a: Int, b: Int): Int {
    return if (a < b) b else a
}