[Python/파이썬] 백준 10942번: 팰린드롬?

문제

 

풀이

dp[i][j] : i ~ j까지의 수열이 팰린드롬인지 저장

ex) dp[1][3] = True : 1 ~ 3까지의 수열이 팰린드롬 수

arr 배열에 전체 수열 저장

 

1. 원소가 하나인 경우 무조건 팰린드롬 수

dp[0][0], dp[1][1], ... dp[n][n] = True

 

2. arr[i] == arr[i+1]인 경우 팰린드롬 수 (부분 수열의 길이가 2이고, 원소가 동일한 경우)

ex) 11, 22, 33, 44 는 팰린드롬 수

 

3. a~b까지의 수열에서 arr[a] == arr[b]이고 그 사이의 수열이 팰린드롬인 경우

 

 

원소가 4개인 경우, 5개인 경우 ... 반복하면 된다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n - i):
        if arr[j] == arr[j + i]:
            if i < 2:
                dp[j][i + j] = 1
            elif dp[j + 1][i + j - 1] == 1:
                dp[j][i + j] = 1
           

r = int(input())
for _ in range(r):
    a, b = map(int, input().split())
    print(dp[a - 1][b - 1])

 

마무리

팰린드롬은 어느정도 마스터한 것 같다 ㅎㅎ