[백준 - Python] 10942 - 펠린드롬?

0. 문제 링크

 

 

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

10942번: 팰린드롬?

---

1. 풀이 방법

 

 

만약 2~4까지 펠린드롬이라고 가정해보자.

그러면 1~5까지 펠린드롬인지는 어떻게 알 수 있을까?

바로 1번째와 5번째가 맞는지 비교하고, 2~4가 펠린드롬인지 확인하면 되는 것이다.

따라서 n~m까지 펠린드롬인지 확인하기 위해서는, n-1~m-1이 펠린드롬인지 확인하고, n번째와 m번째가 펠린드롬인지 확인하면 된다.

숫자가 하나만 있는 경우는 무조건 펠린드롬이고, 2개가 있는 경우에는 맞는지 확인만 하면 된다.

3개부터는 양 끝단의 숫자가 맞는지 확인하면 된다. 어차피 중간에 있는 숫자는 하나뿐이므로 무조건 펠린드롬이 되기 때문!

그냥...이런 방식을 쓰면 된다.

이렇게 우선 dp 배열을 만들어놓고, 들어오는 범위에 따라서 맞는지 아닌지만 출력하면 된다.

---

2. 코드

 

 

import sys


def sol():
    n = int(sys.stdin.readline().strip())
    board = list(sys.stdin.readline().split())
    m = int(sys.stdin.readline().strip())
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1
    for i in range(n - 1):
        dp[i][i + 1] = 1 if board[i] == board[i + 1] else 0     # i부터 i + 1번째까지
    for i in range(n - 2):
        dp[i][i + 2] = 1 if board[i] == board[i + 2] else 0
    for i in range(n - 3):
        dp[i][i + 3] = 1 if board[i] == board[i + 3] and board[i + 1] == board[i + 2] else 0

    for j in range(4, n):      # i로부터 2칸 떨어진 애들부터 봄
        for i in range(n - j):       # i부터 i + j까지 팰린드롬인지 봄, 2칸 떨어진 애들을 본다면 0~2, 1~3, 2~4가 최대 범위임
            if board[i] == board[i + j] and dp[i + 1][i + j - 1]:       # i와 i + j번째가 같고, i + 1 ~ i + j - 1이 팰린드롬이라면 i ~ i + j도 팰린드롬임
                dp[i][i + j] = 1

    for _ in range(m):
        s, e = map(int, sys.stdin.readline().split())
        print(dp[s - 1][e - 1])


sol()

---

3. 마무리