[백준 10942 🥇] 팰림드롬?

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

10942번: 팰린드롬?

문제

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

먼저, 홍준이는 자연수 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개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

 

문제풀이

import sys

# 숫자의 개수
n=int(sys.stdin.readline())
numbers=list(map(int, sys.stdin.readline().split(' ')))
# dummy
numbers.insert(0,0)
# 질문의 개수
m=int(sys.stdin.readline())


dp=[[False]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
    dp[i][i]=True

for i in range(1, n):
    if numbers[i]==numbers[i+1]:
        dp[i][i+1]=True


for i in range(3,n+1):
    for j in range(1,i-1):
        if numbers[i]==numbers[j] and dp[j+1][i-1]:
            dp[j][i]=True


for _ in range(m):
    s,e=map(int, sys.stdin.readline().split(' '))
    # 시간 초과 코드(최악의 경우 10^6*10^3)
    # check=numbers[s:e+1]
    # for i in range(len(check)//2):
    #     if check[i]==check[len(check)-i-1]:
    #         continue
    #     else:
    #         print(0)
    #         break
    # else:
    #     print(1)
    if dp[s][e]:
        print(1)
    else:
        print(0)

처음에 시간 초과가 발생했다. 문제의 개수인 m이 최대 1,000,000이었고, 숫자의 개수인 n이 최대 2,000이었으므로 최악의 경우엔 10^9였기 때문에 당연하게도 시간초과가 발생했다. 

 

고민을 하다 DP를 이용해서 풀어보기로 했다. 

1 2 1 3 1 2 1

숫자가 위의 형식과 같을 때, DP 배열의 상태는 다음과 같다. 

같은 인덱스끼리는 숫자가 한 개이므로 팰린드롬 성립

1번부터 3번까지 팰린드롬 성립

1번부터 7번까지 팰린드롬 성립

2번부터 6번까지 팰린드롬 성립

.

.

.

위와 같은 형식으로 팰린드롬의 성립을 저장해줬다. 

팰린드롬의 성립은 numbers[i]==numbers[j]이면서 dp[j+1][i-1]이 True일 때 성립한다. 

 

위 코드에서는 우선 dp[i][i]는 모두 True로 초기화해주고, 연달아 붙어 있는 두 개의 수가 동일할 경우에 dp[i][i+1]을 True로 초기화해줬다. 

그리고, 나머지는 numbers[i]==numbers[j]이면서 dp[j+1][i-1]인지 확인하면서 성립하면 True를 저장해줬다. 

화살표를 친 방향으로 DP 값을 채워줘야 제대로 값이 들어가고, 파란색 원에 해당하는 부분은 앞선 2개의 for문으로 값이 들어갔기 때문에 

for i in range(3,n+1):
    for j in range(1,i-1):
        if numbers[i]==numbers[j] and dp[j+1][i-1]:
            dp[j][i]=True

위와 같이 탐색하는 인덱스를 설정했다. 

 

그리고 문제들을 입력받으면서 dp[s][e]가 True면 1을 출력하고, False면 0을 출력하도록 했다.