[백준] 10942번 - 팰린드롬? (파이썬/C++)

문제) 백준 - 동적 계획법 (Dynamic programming) - 팰린드롬?

-> www.acmicpc.net/problem/10942

10942번: 팰린드롬?

 

dp를 n x n의 2차원 배열로 선언한다. 예를 들어 리스트의 인덱스에 대해 1부터 3까지 팰린드롬이라면, dp[1][3] = True로 설정한다. 즉, 부분 리스트 인덱스의 시작 start와 인덱스의 끝 end를 이용해 검사해  팰린드롬일 경우 dp[start][end]를 True, 아닐 경우 False로 정한다.

 

팰린드롬의 검사는 검사하려는 부분 리스트의 내부 리스트(start + 1 ~ end - 1)가 팰린드롬인지 검사하고, 추가되는 리스트(start, end)를 검사해 둘이 같다면 팰린드롬이다. 

 

 

즉, 어떤 리스트가 팰린드롬이고 양 옆 인덱스의 값이 같다면 새로운 리스트 또한 팰린드롬이다.

 

 

파이썬 소스 코드)

import sys
input = sys.stdin.readline

n = int(input())

dp = [[False] * n for i in range(n)]
num = list(map(int, input().split()))

for idx in range(n):
    for start in range(n):
        end = start + idx
        if end >= n:
            break

        if idx == 0:
            dp[start][end] = True
            continue

        if idx == 1:
            if num[start] == num[end]:
                dp[start][end] = True
                continue
        if num[start] == num[end] and dp[start + 1][end - 1]:
            dp[start][end] = True

m = int(input())
for i in range(m):
    a, b = map(int, input().split())
    if dp[a - 1][b - 1]:
        print(1)
    else:
        print(0)

---

 

C++ 소스 코드)

 

 

 

 

ps. Top-down 방식에 미쳐있지 말자!