10942. [Python]팰린드롬?

1. 문제

 

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

10942번: 팰린드롬?

 

2. 접근 방법

 

• 시간 제한: 0.5초
• 메모리 제한: 256MB
• DP(다이나믹 프로그래밍)

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline
# 숫자의 길이
N = int(input())
# 숫자 리스트
num_list = list(map(int,input().split()))
# 반복문 횟수
M = int(input())
# 각 숫자들 인덱스별 팰린드롬 체크 배열
ans_list = [ [0] * N for _ in range(N)]
# 1~1 2~2 등 자기자신은 팰린드롬 이므로 1 대입
for i in range(N):
    ans_list[i][i] = 1
# 2 까지는 i와 i+1 만 비교해도됨
for i in range(N-1):
    j = i + 1
    if num_list[i] == num_list[j]:
        ans_list[i][j] = 1
# 2 이상부터 반복문
if N > 2:
    # 3이 초기값이므로 3부터 반복문
    for i in range(3,N+1):
        # 0부터 N에서 i 를 뺸 길이만큼 반복
        for j in range(N-i+1):
            # index 라는 변수를 통해서 0 부터 몇번 인덱스까지 비교할지 대입
            index = j + i - 1
            # num_list의 index 와 j 값이 같은 값이고 팰린드롬 체크하는 ans_list에 index 와 j 값을 각각 +-1한 인덱스가 팰린드롬인 경우
            if num_list[index] == num_list[j] and ans_list[j+1][index-1] == 1:
                # ans_list[j][index] 도 팰린드롬 이므로 1 넣어줌
                ans_list[j][index] = 1

for _ in range(M):
    start, end = map(int,input().split())
    start -= 1
    end -= 1
    print(ans_list[start][end])

 

4. 문제를 풀고난 후 생각

 

• 이 문제가 왜 DP문제인지 의아할 수 있다. 하지만 문제를 풀때 투 포인터나 이중for문을 사용해 인덱스를 비교하면 시간초과가 나기 때문에 다른 방식을 생각해봐야 한다.
• 불필요한 연산을 제거하기 위해 start, end 가 같은 경우 1~1 / 2~2 등 값은 바로 1로 처리해버렸고, 2의 경우 반복문의 값 +1 을해가며 비교를 통해 같으면 1을 넣어줬다.
• ans_list 라는 리스트가 이제 DP를 동작할 리스트가 되는데 이 리스트의 경우 
  
  예시로 1 2 1 1 2 1 이라는 숫자리스트가 있으면
  0번 인덱스 : 팰린드롬체크 => 1 0 1 0 0 1
  1번 인덱스 : 팰린드롬체크 => 0 1 0 0 1 0 ....
  이렇게 각 인덱스의 숫자가 0~1 길이가 팰린드롬인지 체크 해주는 숫자가된다.
  
  
• 바로 위의 예시를 통해 1~1 , 1~2 까지 팰린드롬 체크는 위의 반복문에서 진행했기 때문에 1~3이 팰린드롬인지 체크하면 된다.
• 1과 3의 값이 같으면 1~2 까지가 팰린드롬이였는지 값을 보기위해 index-1 과 j+1 이 1인지 확인을 했다.
• 반복문은 0부터 N-i 까지 하기때문에 이전값을 활용하여 팰린드롬 체크를 쌓아가기 때문에 DP 문제로 분류된 것 같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(다이나믹 프로그래밍)