[DP] 백준 10942번 “팰린드롬?” Python 풀이

문제 링크

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

풀이

• 2차원 DP 테이블을 채우는게 핵심입니다.

  • DP[i][j]는, i 부터 j 까지의 숫자가 팰린드롬인지 아닌지를 나타냅니다.

• DP 테이블은 아래 조건을 통해 채워나갑니다.

  1. 연속된 숫자가 1개일 경우엔, 무조건 팰린드롬입니다.
  2. 연속된 숫자가 2개일 경우엔, 양끝 숫자가 같다면 팰린드롬입니다.
  3. 연속된 숫자가 3개 이상일 경우엔, 양끝 숫자가 같고, 그 사이의 숫자들이 팰린드롬이라면, 팰린드롬입니다.

• 따라서, 1번과 2번 조건을 실행한다면 DP 테이블은 아래와 같이 채워집니다.

  

• 이후, 3번 조건을 실행한다면, DP 테이블의 하향 대각선이 차례대로 채워집니다.

  • 연속된 숫자가 3개일 때는, 세번째 하향 대각선
  • 연속된 숫자가 4개일 때는, 네번째 하향 대각선
  • 연속된 숫자가 5개일 때는, 다섯번째 하향 대각선
  • 연속된 숫자가 6개일 때는, 여섯번째 하향 대각선
  • 연속된 숫자가 7개일 때는, 일곱번째 하향 대각선

• 최종적으로, DP 테이블은 아래와 같이 완성됩니다.

  

코드

import sys

# 수열의 크기 N
n = int(sys.stdin.readline())
# 칠판에 적은 수 N개
array = list(map(int, sys.stdin.readline().split()))
# 각 숫자간의 팰린트롬 정보를 저장하는 DP 테이블
dp = [[0] * n for _ in range(n)]

# 연속된 숫자가 1개일 경우
for i in range(n):
    dp[i][i] = 1

# 연속된 숫자가 2개일 경우
for i in range(n-1):
    # 양끝 숫자가 같다면
    if (array[i] == array[i+1]):
        dp[i][i+1] = 1
    # 양끝 숫자가 다르다면
    else:
        dp[i][i+1] = 0

# 연속된 숫자가 3개 이상일 경우

# 연속된 숫자의 개수
for continue_number in range(3, n+1):
    # 첫 인덱스
    for start in range(n - continue_number + 1):
        # 마지막 인덱스
        end = start + continue_number - 1

        # 양끝 숫자가 같고, 그 사이의 숫자들이 팰린드롬이라면
        if (array[start] == array[end] and dp[start+1][end-1] == 1):
            dp[start][end] = 1

# 질문의 개수 M
m = int(sys.stdin.readline())

# 각 질문
for _ in range(m):
    s, e = map(int, sys.stdin.readline().split())

    # 팰린드롬 결과 출력
    print(dp[s-1][e-1])

참고

• https://ddiyeon.tistory.com/73?category=942063