[백준 10942번] 팰린드롬?

http://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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

 

# 접근 방법

• dp를 이용해주어 풀면 된다.
• 부분 문자열 table에 하위 문자열의 회문 여부를 저장하여 이전 결과를 사용해준다.
• 이 경우 2개의 for문을 사용하므로 O(N^2)의 시간복잡도를 가지게 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
  
N = int(input())  
nums = [False] + [*map(int, input().split())]  
M = int(input())  
  
dp = [[0] * (N+1) for _ in range(N+1)]  
# 각 한 단어씩은 팰린드롬 이므로 True 체크  
  
for i in range(1,N+1):  
    dp[i][i] = True  
  
# 11, 22와 같이 연속된 값인 경우 팰린드롬이므로 True  
for j in range(1, N):  
    if nums[j] == nums[j+1]:  
        dp[j][j+1] = True  
  
# k만큼씩 떨어진 단어 체크  
# 이 때, 하위 단어에 회문이 존재한다면 # dp[l][u]를 True로 변경  
for k in range(1, N+1):  
    for l in range(1, N-k+1):  
        u = k+l  
        if nums[l] == nums[u] and dp[l+1][u-1]:  
            dp[l][u] = True  
  
  
for _ in range(M):  
    a, b = map(int, input().split())  
    print(1 if dp[a][b] else 0)