<백준> 팰린드롬(Gold 4)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/팰린드롬? at main · heesoo-park/ForCodeKata

제출 결과

---

오늘 이 문제는 보자마자 DP구나... 라는 생각이 들었다.

팰린드롬은 회문을 말한다. 앞으로 읽어도 뒤로 읽어도 같은 문장

미리 DP 배열을 이용해 회문이지 체크를 하고 질문을 받아 해결해야지 시간 안에 통과할 수 있을 것이기 때문이다.

 

범위가 1일 때는 무조건 회문이라고 볼 수 있다.

범위가 2일 때는 두 개의 숫자가 같을 때 회문이라고 할 수 있다.

범위가 3일 때부터는 양 끝의 숫자가 같고 그 안의 범위 내 수열이 회문일 때 회문이라고 할 수 있다.

 

그래서 DP 배열을 S부터 E까지가 회문인지 체크하는 배열로 잡았다.

dp[1][1] 이라고 하면 '1부터 1까지의 범위의 수열은 회문인가?' 가 된다.

 

범위가 1일 때와 2일 때는 초기값이 되기 때문에 반복문을 돌며 값을 넣어줬고 3일 때부터는 2중 for문을 돌며 조건을 확인하고 값을 넣었다.

여기의 2중 for문은 범위가 2000까지인 n을 도는 것이기 때문에 제한 시간에 걸릴 염려가 없다.

 

약간 이해하기가 쉽지는 않았지만 잘 접근해서 해결한 것 같아 다행이다.

이 문제를 풀며 dp 배열을 채울 때 범위의 개념에서도 볼 수 있겠다는 아이디어를 얻게 됐다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))) {
    lateinit var st: StringTokenizer
    val sb = StringBuilder()
    
    val n = readLine().toInt()
    
    val list = IntArray(n + 1)
    st = StringTokenizer(readLine())
    for (i in 1..n) {
        list[i] = st.nextToken().toInt()
    }
    
    val dp = Array(n + 1) { BooleanArray(n + 1) }
    for (i in 1..n) {
        dp[i][i] = true
        if (i != 1 && list[i - 1] == list[i]) dp[i - 1][i] = true
    }
    
    for (j in 2..n - 1) {
        for (i in 1..n) {
            if (i + j > n) break
            
            if (list[i] == list[i + j] && dp[i + 1][i + j - 1]) dp[i][i + j] = true
        }
    }
    
    var m = readLine().toInt()
    while (m-- > 0) {
        val (s, e) = readLine().split(' ').map { it.toInt() }
        sb.append(if (dp[s][e]) 1 else 0).append('\n')
    }
    
    print(sb)
}