[백준 10942] 팰린드롬?

문제

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

10942번: 팰린드롬?

---

아이디어

주어진 N개의 자연수의 S번째부터 E번째까지의 수가 팰린드롬을 이루는지의 여부를 나타내는 2차원 배열을 이용한다.

 

즉, N×N의 배열을 초기화한 후, S번째부터 E번째까지의 수가 팰린드롬을 이루는 경우는 배열의 (S, E)번째 성분을 1로, 팰린드롬을 이루지 않는 경우는 0으로 둔다. 

 

이 문제는 크게 3가지로 나눌 수 있다. 

- 주어진 숫자열의 길이가 1인 경우(즉, S = E인 경우)

- 주어진 숫자열의 길이가 2인 경우(즉, S = E + 1인 경우)

- 주어진 숫자열의 길이가 2보다 큰 경우(즉, S > E + 1)인 경우

 

따라서, 다음의 과정을 이용해서 해를 구한다.

step 3 주어진 숫자열의 길이가 2보다 큰 경우

1. 주어진 숫자열의 길이가 1인 경우는 무조건 팰린드롬을 이룬다.
   
   • N×N 배열의 대각 성분은 1로 채운다.
2. 주어진 숫자열의 길이가 2인 경우는 두 숫자가 같으면 팰린드롬을 이룬다. 
   • 두 숫자가 같은 경우 N×N 배열의 (i,j), j = i+1 성분을 1로 채운다.
   • 두 숫자가 같지 않은 경우 N×N 배열의 (i,j), j = i+1 성분을 0으로 채운다.
3. 주어진 숫자열의 길이가 2보다 큰 경우는 양 끝의 숫자가 같은 경우 양 끝을 제외한 숫자가 팰린드롬을 이루는지를 확인한다.
   
   • 가장 먼저 숫자열의 길이를 고려해야 한다. 숫자열의 길이는 최소 3부터 최대 t가 될 수 있다. 숫자열의 길이에 따라 S가 가질 수 있는 값의 범위는 달라진다.
     
     1. 길이가 3인 경우는 max(S) = t - 3 [alpha = 0]
     2. 길이가 4인 경우는 max(S) = t - 4 [alpha = 1]
     3. ...
     4. 길이가 t인 경우는 max(S) = 0 [alpha = t-3]
     5. 즉, alpha의 범위는 range(t-2)로 순회할 수 있다. 
   • range(t-2)의 alpha에 대해서, 
     • S + alpha + 2 는 최대 t - 1이다(t - 1이 마지막 숫자의 index이기 때문).
       • S의 최댓값은 t - alpha - 3이다. 
       • 즉, S의 범위는 range(t - alpha - 3)으로 순회할 수 있다.
     • E의 값은 S + 2 + alpha 로 정의할 수 있다.
     • 양 끝의 숫자가 같지 않다면 팰린드롬이 성립하지 않기 때문에 배열의 (S, E)성분을 0으로 채운다.
     • 양 끝의 숫자가 같다면, 팰린드롬이 될 수도 있고 그렇지 않을 수도 있다. 
       • 양 끝의 숫자를 제외한 숫자가 팰린드롬을 이룬다면 이 숫자열은 팰린드롬을 이룬다. 
       • 양 끝의 숫자를 제외한 숫자가 팰린드롬을 이루지 않는다면 이 숫자열은 팰린드롬을 이루지 않는다. 
       • 양 끝의 숫자를 제외한 숫자가 팰린드롬인지의 여부가 이미 계산되었는가? Yes
         • 예를 들어, (10, 15)의 숫자열이 팰린드롬을 이루는지를 탐색하는 경우의 과정을 보자.
           1. 숫자열의 양 끝이 같다고 가정하면, (11, 14)에 대해서 팰린드롬을 이루는지의 여부를 탐색한다.
           2. 이 경우에도 같다고 가정하면 (12, 13)에 대해서 팰린드롬을 이루는지의 여부를 탐색한다.
           3. (S, E)에 대해서 E = S + 1의 경우에 대해서는 이미 배열에 정보가 입력되어있기 때문에 팰린드롬을 이루는지의 여부를 계산할 수 있다.

길이가 3 이상인 숫자열의 팰림드롬 여부를 메모이제이션 기법으로 확인하는 방법

Solution

import sys 

t = int(input())
lst = list(input().split())
res = [[0 for _ in range(t)] for _ in range(t)]

for i in range(t) : 
    res[i][i] = 1 
    
for i in range(t-1) : 
    if lst[i] == lst[i+1] :
        res[i][i+1] = 1
        
for alpha in range(t-2) : 
    for s in range(t-2-alpha) :
        e = s + 2 + alpha
        if lst[s] == lst[e] and res[s+1][e-1] == 1 :
            res[s][e] = 1
            
k = int(input())
for _ in range(k) :
    m, n = map(int, sys.stdin.readline().split())
    print(res[m-1][n-1])