[Python/Kotlin] 백준 9251번 : LCS

백준 문제 주소 https://www.acmicpc.net/problem/9251

문제

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

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

입력

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

ACAYKP
CAPCAK

출력

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

4

---

동적계획법 시리즈를 풀고있다보니 이제 문제를 풀 준비로 dp 배열을 만드는 것, 최솟값을 구한다면 min 함수를 사용하고 최댓값을 구한다면 max를 사용하는 것이 바로 생각이 난다.

이 문제도 바로 최대 길이를 찾아낼 수 없기 때문에, 아래부터 차근차근 더해가면서 계산을 해야할 것 같았다.

이 시리즈를 풀면서 많이 사용한 방법인데, 2차원 배열을 만들어서 그 전의 값과 비교한 다음 큰 것을 넣어주는 방법을 사용할 것이다.
이 문제를 풀 때, 주의할 점은 한 문자열에 같은 알파벳이 포함되어 있어도 중복으로 세지 않는 것이다. 따라서 평소 점화식과는 좀 다르게 나뉘게 된다.
첫 번째와 두 번째 문자열의 요소가 같을 때, 글자 추가 전 값에서 1을 더해준다.
dp[i][j] = dp[i-1][j-1] + 1
첫 번째와 두 번째 문자열의 요소가 같지 않을 때, 이전까지 비교한 값들 중에 최대 값을 넣는다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Python 풀이(실패)

n, m = input(), input()
h = len(n)
dp = [[0 for _ in range(h+1)] for _ in range(h+1)]

for i in range(1, h+1):
    for j in range(1, h+1):
        if n[i-1] == m[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
print(dp[-1][-1])

백준에서 런타임에러(IndexError)가 발생했다. index-1을 사용하기 때문에 1부터 반복문을 돌렸는데 어디서 오류가 나는지 모르겠어서 이 문제로 고민을 길게 했다. 문제였던 부분은 입력이었는데, 예제 입력과 다르게 실제 입력들은 두 문자열의 길이가 다를 수 있었다. 문제에서 두 문자열의 길이가 같다는 부분이 없었는데 예제 입력만 보고 같다고 생각하고 코드를 짠 것이었다.

Python 풀이(성공)

n, m = input(), input()
w, h = len(n), len(m)
dp = [[0 for _ in range(w+1)] for _ in range(h+1)]

for i in range(1, h+1):
    for j in range(1, w+1):
        if m[i-1] == n[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
print(dp[-1][-1])

w와 h, m과 n에 대하여 index를 잘 맞춰줘야지 IndexError가 발생하지 않았다.

Kotlin 풀이

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine()
    val m = br.readLine()
    val dp = Array(m.length+1){ Array(n.length+1){0} }

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

    println(dp[h][w])
}