[스위프트][백준 5502][💛골드 3] (다이나믹 프로그래밍)

🧞‍♂️ 난이도

💛 골드 3

🧞‍♂️ 문제

팰린드롬

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

🧞‍♂️ 유형

다이나믹 프로그래밍

🧞‍♂️ 내 풀이

이 문제는 LCS(Least Common Subsequence) 를 그대로 사용하면 되는 문제이다.

LCS 알고리즘은 다음과 같다

두개의 원소가 같을때

dp[i][j] = dp[i-1][j-1] + 1

다를때

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

그래서 주어진 문자열이랑 그 문자열을 뒤집은 문자열로 LCS 길이를 구해서 N 에서 빼면 된다.

---

🧞‍♂️ 스위프트 풀이

import Foundation

let N = Int(readLine()!)!
let word = readLine()!.map { String($0) }
let reversedWord = word.reversed().map { $0 }

var dp = [[Int]].init(repeating: [Int](repeating: 0, count: N+1), count: N+1)


for i in 1..<N+1 {
    for j in 1..<N+1 {
        if word[i-1] == reversedWord[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(N - dp[N][N])

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기