백준 10942 팰린드롬? Kotlin (dp)

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

10942번: 팰린드롬?

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

입력과 문제 이름을 봤을 때 DP 냄새가 솔솔 나는 문제이다.

바로 점화식을 구해보자.

우선 팰린드롬을 어떻게 dp와 연결시킬지 생각해 보면,

"abcde"이 있다고 할 때

a부터 e까지의 숫자가 팰린드롬이려면  a == e && b~d == 팰린드롬 이어야 한다.

b부터 d까지의 숫자가 팰린드롬이려면 b == e && c~c == 팰린드롬 이어야 한다.

뭔가 감이 잡힌다.

c~c는 즉, 길이가 1인 숫자는 무조건 팰린드롬이다.

그럼 길이가 2일 땐? 3일 땐? 4일 땐?

모든 숫자들에 대해 해당 숫자의 1부터 N까지 길이만큼의 숫자가 팰린드롬인지 미리 dp에 저장해두면 되는 것이다.

따라서 식은 다음과 같다.

dp[s][s + 길이] = arr[s] == arr[s+길이] && (dp[s+1][s+길이-1]  == 팰린드롬 || s+1 > s+길이-1)

코드

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

fun main() = with(System.out.bufferedWriter()){
    //input
    val n = getInt()
    val arr = getIntList()
    val m = getInt()

    //solve
    val dp = Array(n+1){ i->
        BooleanArray(n+1){ j->
            i==j
        }
    }
    for(i in 1 until n){
        for(j in 0 until n-i){
            dp[j][j+i] = arr[j] == arr[j+i] && (dp[j+1][j+i-1] || j+1 > j+i-1)
       }
    }
    repeat(m){
        val (s,e) = getIntList().map { it-1 }
        write("${if(dp[s][e]) 1 else 0}\n")
    }
    close()
}