[6개월 안에 백준 플래티넘 달성하기] 20. 팰린드롬? 10942

팰린드롬? 10942

10942번: 팰린드롬?

 

이중 배열을 이용한 DP문제입니다.

마치 처음 dp문제를 풀었을 때와 같이 어렵습니다.

문제를 보고 이중 배열 DP에 대한 아이디어를 떠올리기 조차 쉽지 않을뿐더러 알고 있다 하더라도 이중 배열에 적용가능한 규칙을 찾는 것 또한 어렵습니다.

 

많이 풀어봐야 될 거 같습니다.

문제

 

풀이

처음에는 딱히 아이디어가 떠오르지 않아서 모든 경우의 팰린드롬을 구해주었습니다. 이런 방식으로 풀어줘도 입력되는 수 자체가 작기 때문에 통과가 됩니다.

 

하지만 출제자의 의도는 해당 풀이가 아니기 때문에 조금 더 아이디어를 생각해 봤습니다.

바로 이전 문제가 이중 배열의 DP문제였기 때문에 쉽게 이중 배열을 떠오를 수 있었습니다. 하지만 해결 방법까지 생각해 내기에는 너무 어려웠고 힌트를 보고 알아차릴 수 있었습니다.

 

양 끝의 글자가 같고 그 내부 문자가 팰린드롬일 때 해당 문자열 또한 팰린드롬이다.

 

예를 들어

ex) [1 2 2 3 1 3 2]

- 2 3 1 3 2의 경우 	
  양 끝의 글자는 2로 동일하고 
  그 내부 3 1 3은 팰린드롬이기에 해당 문자열 또한 팰린드롬이 됩니다.

 

 

어찌 보면 당연한 소리 같지만 이 당연한 소리로 인해 어느 정도 규칙을 얻을 수 있게 되었습니다.

바로 현재 문자의 팰린드롬을 구하기 위해서는 현재 문자보다 적은 글자의 팰린드롬을 알고 있으면 됩니다.

 

따라서 우리는 

행 : 글자 수, 열 : 글자 인 이중 배열을 만들어 준 뒤 차례대로 값을 추가해 주면 됩니다.

 

이제 예시와 함께 규칙을 찾아보겠습니다.

 

인덱스 y = 6, x = 0 일 때의 의미는

문자 1부터 시작해서 7글자인 [1 2 1 3 1 2 1] 를 의미합니다. 우리는 바로 해당 문자가 팰린드롬인 것을 알고 있지만 모른다고 가정하고 배열에 있는 값을 통해서 알아보고자 합니다.

y=6 x=0

 

일단 첫 글자랑 마지막 글자가 같은지 확인해 줍니다.

첫 글자의 인덱스는 x이며 마지막 글자의 인덱서는 x + y(글자개수)가 됩니다.

if (arr[x] == arr[x+y])

 

그다음 내부 문자열이 팰린드롬인지 확인해 줍니다.

내부 문자열의 글자 개수는 양 끝 글자를 제외한 y-2이며 시작 글자의 인덱스는 x+1입니다.

if (arr[x] == arr[x+y] && dp[y-2][x+1] == 1)

// 위랑 동일하게 작동
if (arr[x] == arr[x+y]) {
    dp[y][x] = dp[y-2][x+1]
}

 

 

결과적으로 y, x가 주어졌을 때 이중 배열 dp에서 dp[y-2][x+1] 의 값을 알고 있다면 팰린드롬 여부를 알 수 있습니다.

단. y-2의 값들을 알기 위해서는 글자 개수가 1개, 2개일 경우의 값은 직접 추가해줘야 합니다.

 

초기 세팅

최종 DP

 

코드를 보시면 더 쉽게 이해하실 겁니다.

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run{
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    val N =input()
    val arr = IntArray(N) {input()}
    val dp = Array(N) {BooleanArray(N)}  // 행 : 글자수, 열 : 시작 글자

    for (i in 0 until N) dp[0][i] = true  // 글자가 하나인 경우 모두 팰린드롬
    for (i in 0 until N-1)                // 나중에 i-2값 때문에 두 글자까지 임의로 채워넣어줌
        if (arr[i] == arr[i+1]) dp[1][i] = true


    for (i in 2 until N) {
        for (j in 0 until N-i) {
            // 현재 문자에서 양 끝을 제거한 문자가 팰린드롬인 경우
            if (arr[j] == arr[j+i]) {
                dp[i][j] = dp[i-2][j+1] // 현재 문자에서 양 끝을 제거한 문자가 팰린드롬인지 여부에 따라 결정
            }
        }
    }

    val sb = StringBuilder()
    repeat(input()) {
        val start = input()-1
        val end = input()-1
        sb.appendLine(if (dp[end-start][start]) 1 else 0) // 행 : 글자 개수, 열 : 시작 글자
    }

    print(sb)
}