[백준] 10942번: 펠린드롬?

이 문제는 펠린드롬 판정만 하면 되는 쉬운 문제였다.
근데 그동안 dp문제를 푼 방식이랑은 조금 달라서 다른 블로그를 보고서야 맞았습니다를 볼 수 있었다.

이 전에 펠린드롬을 처음으로 본 문제는 수열이 주어졌을 때 가장 긴 펠린드롬의 길이를 구하는 것이었다. 그 때보다 알고리즘은 훨씬 간단했다.

처음에 혹시 몰라 제출해봤는데 시간초과가 난 코드다. (메모이제이션 X)

N = int(input())
arr = list(map(int, input().split()))
M = int(input())
for _ in range(M):
	S, E = map(int, input().split())
	S -= 1
	E -= 1
	if (S - E) % 2: # if arr length is odd
		limit = (S + E) // 2 - S
	else:
		limit = (S + E) // 2 - S + 1
	isPelindrom = True
	for idx in range(limit):
		if arr[S+idx] != arr[E-idx]:
			isPelindrom = False
			break
	if isPelindrom:
		print(1)
	else:
		print(0)

길이가 짝수일 때와 홀수일 때를 나눠서 판별했다. 근데 여기서 dp를 어떻게 써야될 지 모르겠는 게 참.. 당황스러웠다. 저 코드에서는 dp를 선언해도 딱히 쓸모가 없었다. 어차피 모든 idx에 대해서 검사해야하는 방식이었기 때문이다 🤢

그래서 방식을 바꾸어야했다🥱 모든 가능한 s와 e에 대한 펠린드롬 여부 dp[s][e]를 먼저 싹 다 계산하고 나중에 질문에 답할 때 그냥 dp[s][e]를 출력하는 방법이었다.

import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
M = int(input())

dp = [[-1 for _ in range(N)] for _ in range(N)]
# dp 초기조건
for i in range(N):
	dp[i][i] = 1 # s=e 이면 무조건 펠린드롬
	if i < N-1:  # s, e가 연속하는 수일 때는 두 수만 비교해서 판별
		dp[i][i+1] = 1 if arr[i] == arr[i+1] else 0
# 반복문으로 dp 계산
for i in range(N):
	for j in range(i):
		dp[j][i] = 1 if (dp[j+1][i-1] and arr[j] == arr[i]) else 0

# M개의 질문에 답하기			
for _ in range(M):
	s, e = map(int, input().split())
	s -= 1
	e -= 1
	print(dp[s][e])

처음에 파이썬으로 제출하면 계속 틀려서 c로 작성한 코드다. 이 코드도 마찬가지로 처음에 초기값(s=e, s+1=e 인 경우)만 잘 설정해주고 나서 모든 dp값을 계산해놓는다.

#include <stdio.h>

int dp[2000][2000];
int main(){
	int N;
	scanf("%d", &N);
	int arr[N];
	for(int i = 0; i < N; i++){
		scanf("%d", arr+i);
	}
	for(int i = 0; i < N; i++){
		dp[i][i] = 1;
		if(i < N-1)
			dp[i][i+1] = arr[i] == arr[i+1] ? 1 : 0;
	}	
	for(int i = 0; i < N; i++){
		for(int j = i-2; j >= 0; j--){
			dp[j][i] = dp[j+1][i-1] && (arr[j] == arr[i]) ? 1 : 0;
		}	
	}	
	int M;
	scanf("%d", &M);
	for(int i = 0; i < M; i++){
		int s, e;
		scanf("%d%d", &s, &e);
		printf("%d\n", dp[--s][--e]);
	}	
	return 0;
}