[백준] 10942 팰린드롬? (python 파이썬)

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

10942번: 팰린드롬?

---

배열에서 i부터 j까지가 팰린드롬인지 아닌지 여러 번 확인하는 문제.

 

---

아이디어

1. dp

• 간단하게 리스트 슬라이싱으로는 시간 초과가 나서 dp를 사용
• i번째부터 j까지의 수가 팰린드롬인지 확인한 결과를 저장하기 위해 이차원 리스트를 사용하기로 결정했다.

2. 점화식

• 먼저 무조건 팰린드롬인 i부터 i까지의 수는 1로 저장해둔다.
• 그리고 i번째 수와 i + 1번째 수가 같으면 팰린드롬이니까 이것도 1로 저장.
• 점화식은 이미 팰린드롬인 수 양 옆에 오는 두 수가 같다면 그것도 팰린드롬이다.
• 예를 들어 121이라는 팰린드롬 수에서 양 옆에 3 이 붙는 다면 31213 도 팰린드롬이다.

---

전체 코드

import sys
N = int(input())

num_arr = [int(x) for x in input().split()]

M = int(input())

DP = [[0] * (N) for _ in range(N)] # DP[i][j] i부터 j까지

for i in range(N): # len == 1
    DP[i][i] = 1

for i in range(N - 1): # len == 2
    if num_arr[i] == num_arr[i + 1]:
        DP[i][i + 1] = 1

for num_len in range(2, N): # len >= 3
    for start in range(N - num_len):
        end = start + num_len
        if num_arr[start] == num_arr[end]:
            if DP[start + 1][end - 1] == 1:
                DP[start][end] = 1

for _ in range(M):
    S, E = map(int, sys.stdin.readline().split())
    print(DP[S - 1][E - 1])

---

코드 설명

for i in range(N): # len == 1
    DP[i][i] = 1

for i in range(N - 1): # len == 2
    if num_arr[i] == num_arr[i + 1]:
        DP[i][i + 1] = 1

위에서 설명한 수의 길이가 1이나 2일 때 팰린드롬 인지 확인하는 코드다.

 

for num_len in range(2, N): # len >= 3
    for start in range(N - num_len):
        end = start + num_len
        if num_arr[start] == num_arr[end]:
            if DP[start + 1][end - 1] == 1:
                DP[start][end] = 1

이후 수의 길이가 3 이상인 경우부터 팰린드롬인지 확인해주면 된다.

만약 DP[start + 1][end - 1] == 1(start + 1 번째부터 end - 1까지의 수가 팰린드롬)이고

start번째 수와 end번째 수가 같다면 DP [start][end] = 1이다.

 

이후 이중 for문을 짜는데 주의할 점이 있다.

만약 이중 for문을 그냥 흔히 작성하듯 0 0, 0 1... 이런 식으로 작성하면 오류가 발생한다.

 

예를 들어 DP[2][6]의 값을 정하려면 DP[3][5]의 값을 알아야 한다. 

하지만 일반적인 이중 for문에서는 아직 DP[3][5]의 값이 정해져 있지 않으므로 제대로 값이 입력되지 못한다.

 

이 경우를 피하기 위해서 이중 for문에서 첫 번째 for문을 시작점(start)이 아닌 수의 길이(num_len)로 설정하면 된다.

이렇게 작성하면 이미 이전에 수의 길이가 1과 2 인 것은 이미 확인했으므로 바로 수의 길이가 3인 것부터 차례대로 채워 나가면 된다.