[백준 10942번] 팰린드롬? (python)

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

 

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

 

기록

(dp 17일차) 요즘 술술 풀어서 자만할 뻔 했는데 다시 정신차렸다..!

 

이번 문제는 dp[i][j]에 i~j번째 숫자의 팰린드롬 여부를 저장하며, dp[i][j] = 양 끝 같은지 & 안쪽이 팰린드롬인지(dp[i+1][j-1])를 점화식으로 세워 풀어나간다.

 

문제의 예시를 사용하여 dp 배열을 채워나가는 과정이다. 먼저 숫자가 한 개일 때와 두 개일 때를 초기화 해준다. 한 개일 때는 무조건 팰린드롬, 두 개일 때는 두 숫자가 같으면 팰린드롬, 다르면 팰린드롬이 아니라고 저장한다.

	1	2	1	3	1	2	1
1	O	X
2		O	X
1			O	X
3				O	X
1					O	X
2						O	X
1							O

 

숫자 세 개 부터는 양 끝의 숫자(i번째, j번째)가 같고, 그 사이의 숫자(dp[i+1][j-1])들이 팰린드롬이라면 팰린드롬, 아니라면 팰린드롬이 아니라고 저장한다. 예시로 dp[1][5]를 구해보자. dp[1][5]는 1~5번째 숫자가 팰린드롬인지 여부를 저장한다. 먼저 양 끝 숫자(1번째, 5번째)가 같은 지 확인해보면, 모두 2로 양 끝 숫자는 같다. 다음으로 2~4번째의 숫자가 팰린드롬인지 확인해보면, dp[2][4]는 O로 팰린드롬이라는 것을 알 수 있다. 따라서 dp[1][5]는 팰린드롬이라는 것을 알 수 있다.

	1	2	1	3	1	2	1
1	O	X	O	X	X
2		O	X	X	X	?
1			O	X	O	X
3				O	X	X	X
1					O	X	O
2						O	X
1							O

	1	2	1	3	1	2	1
1	O	X	O	X	X	X	O
2		O	X	X	X	O	X
1			O	X	O	X	X
3				O	X	X	X
1					O	X	O
2						O	X
1							O

최종 dp 배열이 채워진 모습이다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
seq = list(map(int, input().split()))
dp = [[0]*n for i in range(n)]

for i in range(n):
    dp[i][i]=1
for i in range(n-1):
    if seq[i]==seq[i+1] : dp[i][i+1]=1
    else : dp[i][i+1]=0
for cnt in range(n-2):
    for i in range(n-2-cnt):
        j = i+2+cnt
        if seq[i]==seq[j] and dp[i+1][j-1]==1 :
            dp[i][j]=1

m = int(input())
for i in range(m):
    a, b = map(int, input().split())
    print(dp[a-1][b-1])

1. i~j번째 숫자가 팰린드롬인지 저장할 이차원 dp 배열 생성

2. 숫자가 한 개일 경우는 무조건 1로 저장

3. 숫자가 두 개일 경우는 두 숫자를 비교하여 같으면 1, 다르면 0 저장

4. 숫자가 세 개 이상일 경우는 양 끝 숫자가 같고(seq[i]==seq[j]) 그 사이의 숫자가 팰린드롬이면(dp[i+1][j-1]==1) 1을 저장하고, 아니면 0을 저장한다.

5. 테스트케이스의 입력값에 따라 dp에서 a~b 숫자의 팰린드롬 여부를 출력한다.