[백준/c++] 10942번 - 팰린드롬?

문제

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

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.

S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.

S = 3, E = 3인 경우 1은 팰린드롬이다.

S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

풀이과정

1.규칙

• dp이므로 점화식과 메모이제이션을 이용합니다.
• 수열의 크기는 N (1 ≤ N ≤ 2,000) 이고, 홍준의 질문갯수는  M (1 ≤ M ≤ 1,000,000) 입니다.
• 시간 제한 : 0.5 초, 메모리 제한 : 256 MB 입니다.
• 데이터가 적지않은 반면 0.5초라는 시간제한이 있으므로 최대한 빠른 방법을 선택합니다.

2.순서

제 경우, 단순한 for문 펠린드롬코드를 외우고 있는것이 독이 되었습니다.

dp로 풀려면 아예 다른 방식으로 접근해야 했기 때문입니다. T_T

dp로 수열의 S~E가 펠린드롬인지 확인하는 경우는 3가지 입니다.

1. 시작과 끝이 같을경우(길이가 0)

2. 시작과 끝의 차이가 1일 경우(길이가 1)

3. 시작과 끝의 차이가 2이상일 경우(길이가 2이상)

3번의 경우, 그림으로 표현하면

순서로 진행하므로, 점화식은

1. d[n][n] = 1

2. (n는 1~N-1) d[n]와 d[n+1]이 같다면, d[n][n+1] = 1

3. (n는 2~N-1 , m은 1~N-n) pld[m] == pld[n+m] 이고, d[m+1][n+m-1]가 1이라면, d[m][n+m] = 1

3.코드