[백준/Swift] 9251번: LCS

 

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

9251번: LCS

 

최장 공통부분 수열은 연속적으로 공통부분 수열을 찾는 게 아니라, 중간중간 다른 값이 있어도 된다..!

ACAYKP, CAPCAK 를 보면 ACAK

가능한 모든 경우를 구하려면 시간초과가 발생하므로 이럴 땐, dp!

이런 유형은 어떻게 해야 할지 모르겠어서 찾아봤더니, 

  | A C A Y K P
--------------
C |
A | 
P |
C |
A |
K |

 

이런 식으로 진행하면 된다! 이런 방식은 생각 안 해봤는데 좋은 문제를 풀게 되었군.

배열 안 원소는 문자열 A(열)의 원소와 문자열 B(행)의 원소 사이의 최장 공통부분 수열 길이를 넣는 것이다!

DP를 사용하므로 앞 원소의 값을 사용해서 진행하면 되는데!

두 문자열 원소가 같다면, 문자열 A의 이전 문자, 문자열 B의 이전 문자까지 저장된 최장 공통 부분 수열 길이에 + 1

다르면, 문자열 A의 이전 문자까지의 최장 공통 부분 수열 길이, 문자열 B의 이전 문자까지의 최장 공통 부분 수열 길이의 최댓값

이렇게 앞의 값을 이용해서 진행하면, 가장 긴 길이가 나온다!

 

import Foundation

//input
let a = readLine()!.map{ String($0) }
let b = readLine()!.map{ String($0) }
var dp = [[Int]](repeating: [Int](repeating: 0, count: 1001), count: 1001)

//문자열 a를 기준으로
for i in 1...a.count {
    //문자열 b를 순회
    for j in 1...b.count {
        //만약 같은 문자! -> 이전 칸 + 1 (공통문자열길이+1)
        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])

//문자열 a 문자를 시작점으로 b와 비교