====== 팰린드롬? ====== ===== 풀이 ===== * S부터 E까지의 부분문자열이 팰린드롬인지 여부를 저장하는 테이블 dp[S][E]는 2차원 DP를 통해서 O(n^2)에 쉽게 구할수 있다. 이 테이블을 이용하면 각각의 쿼리를 O(1)에 처리할 수 있으므로, 이 방법으로는 총 시간복잡도가 O(n^2+m)이 된다. * S부터 E까지의 부분문자열이 팰린드롬인지 여부를 저장하는 대신, C번째 문자를 중심으로 하는 팰린드롬 중 가장 큰 것의 길이를 저장하는 리스트 dp2[C]를 계산해 둘수도 있다. 이 값들을 갖고도 각각의 쿼리를 역시 O(1)에 처리할수 있다. 그리고 이 값들은 1차원 리스트이므로 공간복잡도가 O(n^2)이 아니라 O(n)이라는 장점이 있다. 나도 이 방법을 사용했다. * dp2[C]도 간단한 DP를 통해서 O(n^2) 시간에 계산이 가능하다. 다만 짝수길이 팰린드롬은 중심에 해당하는 문자가 없으므로, 따로 처리가 필요하다. 첨부한 코드에서는 홀수 길이 팰린드롬을 위한 배열과, 짝수 길이 팰린드롬을 위한 배열을 따로 나눠서 계산했다. * [[ps:가장 긴 팰린드롬 부분문자열|Manacher's algorithm]]을 사용하면 여기서의 dp2배열을 O(n^2)이 아닌 O(n)에 구할 수 있다. 이 알고리즘을 써서 같은 문제를 푸는 코드는 [[ps:problems:boj:11046]]을 참고. ===== 코드 ===== """Solution code for "BOJ 10942. 팰린드롬?". - Problem link: https://www.acmicpc.net/problem/10942 - Solution link: http://www.teferi.net/ps/problems/boj/10942 """ import sys def main(): N = int(sys.stdin.readline()) nums = [int(x) for x in sys.stdin.readline().split()] max_odd_lengths = [] for i in range(N): max_len = -1 for l, r in zip(nums[i:], reversed(nums[:i + 1])): if l != r: break max_len += 2 max_odd_lengths.append(max_len) max_even_lengths = [] for i in range(N - 1): max_len = 0 for l, r in zip(nums[i + 1:], reversed(nums[:i + 1])): if l != r: break max_len += 2 max_even_lengths.append(max_len) M = int(sys.stdin.readline()) for _ in range(M): S, E = [int(x) for x in sys.stdin.readline().split()] length = E - S + 1 max_length = (max_odd_lengths[(S + E) // 2 - 1] if length % 2 else max_even_lengths[(S + E) // 2 - 1]) print('1' if length <= max_length else '0') if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:골드_3}}