[백준 10942] 팰린드롬?

[BanApp]

pypy3

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())

dp = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n - i):

        if j == j+i:
            dp[j][j+i] = 1

        elif arr[j] == arr[j+i]:
            if j + 1 == j+i:
                dp[j][j+i] = 1

            elif dp[j + 1][j+i - 1] == 1:
                dp[j][j+i] = 1

for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())
    print(dp[s - 1][e - 1])

이런 문제가 진정한 dp의 꽃이 아닐까 싶다.
최대한 전에 계산했던 것들을 활용하는 문제다.
우선 0으로 전부 채워진 n by n 리스트를 만든다.
기본적인 원리는 다음과 같다. 시작점과 끝점이 같으면 무조건 펠린드롬 이다.
수열 안에 포함되어 있는 수열들도(여기서는 dp[j+1][j+I-1]을 의미한다.) 펠린드롬 이라면 그 수열도 무조건 펠린드롬이다.
위의 문제의 경우 1 to 7을 탐색한 경우에 다시 7 to 1을 다시 탐색할 필요가 없기 때문에 2중 for문에서 i만큼 줄여가면서 반복해주면 된다.
그러면 해당 dp에 리스트의 인덱스는 각 시작지점과 끝지점을 의미하며 원소는 펠린드롬인지 아닌지 0 과 1로 저장 된다.
호출하면 끝!

[ghdcksgml1]

ㄷㄷ 혹씌 dp성애자이신가요?

팰린드롬 너무 어렵던데 ㅜㅜ

[BanApp]

저는 약간 백트래킹 이나 bfs 문제 나오면 손발 달달떨림니다.. 제 머릿속은 모든 문제는 아이디어 혹은 브루트포스로 풀 수 있다 라는 이분법적 사고이기에..