9251-Swift알고리즘

오랜만에 돌아온 알고리즘 솔루션정리!!!

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

9251번: LCS

오늘의 문제이다! LCS최장 공통 부분 수열을 구하라는 문제!

어떻게 구하면 될까?

1. 맨 마지막문자열부터 비교를 해보면 된다. 

예를들어 이렇게 있을때 만약 맨마지막 문자열이 같다? 하면 이전까지의 최장공통부분수열의 개수 + 1이다.

즉 LCS(i,j) = LCS(i-1, j-1) + 1 이라는 점화식이 나오게 된다. 

그렇다면 다를때는 어떻게 할까? 두번째 사진과 같이K를 끼거나 E를끼거나 혹은 둘다 안끼거나의 방법으로 둘다 함께 낄순 없다. 만약 K를 뺀다고 하면 K를 뺀 나머지 4개의 LCS를 구하면 되는거고 E를 뺀다고 하면 E를 뺀 4개의 LCS를 구하면 된다. 

max(LCS(i,j-1) , LCS(i-1,j-1))이것이 답이 되는것이다. 

//
//  main.swift
//  9251
//
//  Created by 235 on 3/17/24.
//

import Foundation

let a = readLine()!.map{String($0)}
let b = readLine()!.map{String($0)}
var dp = Array(repeating: Array(repeating: 0, count: b.count+1), count: a.count+1)
for i in 1...a.count {
    for j in 1...b.count {
        if a[i-1] == b[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[a.count][b.count])

code로 나타내면 이렇게 된다! 처음에 DP라는 것을 몰라 조금찾아봤지만 .....담엔 풀수 있을듯 싶다 제발