10942 - 팰린드롬? / gold 4 / DP

https://www.acmicpc.net/problem/10942

10942번: 팰린드롬?

- 시간 초과

'''
10942 - 팰린드롬? / gold 4 
'''
import sys

input = sys.stdin.readline


def is_palindrome(start, end, arr):
    flag = 1
    while True:
        if start < end:
            if arr[start] == arr[end]:
                start += 1
                end -= 1
                continue
            else:
                flag = 0
                break
        else:
            break
    print(flag)


n = int(input())
arr = list(map(int, input().split()))
m = int(input())

for _ in range(m):
    s, e = map(int, input().split())
    is_palindrome(s - 1, e - 1, arr)

 

- 정답

'''
10942 - 팰린드롬? / gold 4 / DP
'''
import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
m = int(input())

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

# 길이가 1인 경우
for i in range(n):
    dp[i][i] = 1
# 길이가 2인 경우
for i in range(n - 1):
    if arr[i] == arr[i + 1]:
        dp[i][i + 1] = 1
# 길이가 3이상인 경우
for i in range(2, n):
    for j in range(n - i):
        if arr[j] == arr[i + j] and dp[j + 1][i + j - 1] == 1:
            dp[j][i + j] = 1

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

 

dp 알고리즘

•  dp 리스트를  [0][0] ~ [n-1][n-1] 까지 만들기
  • dp[S-1][E-1] = S에서 부터 E까지 팰린드롬인지 확인
• 길이가 1인경우, EX) s=3, e=3 무조건 팰린드롬이므로, dp[i][i] = 1로 바꾸기
• 길이가 2인경우, arr[i] == arr[i+1] 같으면, dp[i][i+1] = 1 로 바꾸기
• 길이가 3인경우
  • for 문의 i 는 길이를 나타내는 녀석 (2부터 시작 ~ 최대길이 n-1까지)
  • for 문의 j는 해당 인덱스를 가리키는 값 (0부터 ~ n-i 까지)
    • dp 의 인덱스 최대값은 = n-1 이므로, (dp[n - 1][n - 1])
    • i + j 인덱스가 n - 1 보다 무조건 작거나 같아야 하므로
    •  i + j <= n - 1 이다. 
    • j <= n - i - 1 이므로, j 의 범위는 0 ~ n - i - 1 이어야 한다
    • 따라서 for j in range(n - i) 로 코드 설정