백준 1695 팰린드롬 만들기 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

두 가지 풀이가 가능하다.

첫 번째 풀이는

dp[left][right] = left부터 right 인덱스까지 팰린드롬을 만드는 데 필요한 최소 횟수

위의 dp에선 left == right일 경우 dp[left][right] == 0이고, 우리가 구하는 값은

dp[0][n-1]이 된다.

이 dp를 재귀적으로 input[left] == input[right]일 땐 안쪽으로 탐색 (left++, right--)

input[left] != input[right]일 땐 왼쪽을 증가, 오른쪽을 감소 (left++, right--) 두 가지 경우 중 최솟값을 삽입하는 걸로 dp를 채워 정답을 찾을 수 있다.

두 번째 풀이는 LCS를 이용하는 것이다.

LCS를 구하는 풀이는 아래 링크에 있다.

2021.04.28 - [알고리즘 문제 풀이/백준] - 백준 9251 LCS c++

LCS랑 무슨 상관이지? 생각할 수 있다.

예제로 주어진 입력 1 2 3 4 2를 생각해 보자.

얘를 뒤집으면 2 4 3 2 1이다.

이 둘의 LCS를 구하면 2 3 2

팰린드롬은 가운데를 기준으로 양쪽이 같아야 하므로 기존 배열과 거꾸로 뒤집은 배열의 최장 공통 부분 수열을 찾은 것이다.

LCS는 2 3 2

남은 수는 1 4

문제의 조건으로 수를 어디든 끼워넣을 수 있다고 했다.

따라서 2 3 2 1 4든, 2 4 3 2 1이든, 1 4 2 3 2든 LCS를 제외한 1,4만 잘 끼워 넣으면 팰린드롬을 만들 수 있다는 얘기다.

2 3 2 1 4 -> 4 1 2 3 2 1 4

2 4 3 2 1 -> 1 2 4 3 4 2 1

1 4 2 3 2 -> 1 4 2 3 2 4 1

따라서 전체 입력의 크기에 LCS길이(dp[n][n])를 빼주면 된다.

 

 

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    val input = getIntList()
    val reverseInput = input.reversed()
    val dp = Array(n+1){IntArray(n+1)}

    //solve
    //input과 reverseInput의 LCS구해서 전체 사이즈에서 빼기
    for(i in 1 .. n){
        for(j in 1 .. n){
            if(input[i-1] == reverseInput[j-1]){
                dp[i][j] = dp[i-1][j-1]+1
            }
            else{
                dp[i][j] = dp[i-1][j].coerceAtLeast(dp[i][j-1])
            }
        }
    }
    //output
    write("${input.size -dp[n][n]}")
    close()
}