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

문제

 

팰린드롬이란?

앞에서 부터 읽을 때랑 끝에서 부터 읽을때 똑같은 것 , 회문

 

 

 

 

이 문제는 시간을 최대한 최적화하는게 관건인 문제이다. 

범위를 보면 알겠지만 N의 범위는 2000인 반면에 M의 범위가 100만으로 굉장히 큰편이다.

 

 

그래서 100만번 동안 2000개를 확인하면 무조건 시간초과가 나기때문에 어떻게 처리를 해야할지 머리가 아팠던 문제이다..

 

하지만 생각의 전환을 해서  미리 최대 길이 2000의 배열에서 발생할 수 있는 부분배열을 전부 확인해두면 시간 복잡도가 100만번 * 2000이 아니라 2000개를 확인  + 100만이 되므로 시간을 줄일 수 있다.

 

 

그러면 어떻게 모든 부분배열의 경우의 수를 구하는가?

 

 

바로 dp 를 통해서 전부 확인해주면 된다.

 

dp[s][e]가 1이면 s,e 구간이 팰린드롬을 만족하도록 구현해주면된다.

 

일단 dp란 복잡한 문제를 작은 문제로 바꾸어주는 문제이기때문에 작은 것부터 생각해보면 된다.

 

1. s == e일때  즉, 길이가 1인 부분배열

 

 

이때는 무조건 팰린드롬을 만족하므로 1 을 넣어준다

dp = [[0]*n for _ in range(n)]
#길이가 1인 부분배열 처리
for i in range(n):
    dp[i][i] = 1

 

 

2. e-s = 1 즉, 길이가 2인 부분배열

 

이때는 둘이 같아야지만 팰린드롬을 만족한다 ex) 11,22,33...

#길이가 2인 부분배열 처리
for i in range(n-1):
    if nums[i] == nums[i+1]:
        dp[i][i+1] = 1

 

 

그리고 중요한 길이가 3이상인 부분 배열

 

길이가 3이상인 부분배열이 팰린드롬을 만족할라면 s와e 사이에 있는 s-1 ~ e-1 구간의 부분배열이 팰린드롬을 만족해주어야한다. 그리고 s랑 e가 같아야지 s ~ e구간의 부분배열이 팰린드롬을 만족하는게 된다.

 

#cnt + 3 = 현재 확인하는 부분 배열의 길이
for cnt in range(n-2):
    for i in range(n-2-cnt):
        #i가 현재 확인하는 부분배열의 시작점 j는 끝점
        j = i+2+cnt
        if nums[i] == nums[j] and dp[i+1][j-1] == 1:
            dp[i][j] = 1

 

 

이때 for문의 범위를 잡는게 어려웠는데 쉽게 말하자면

 

 

 

cnt가 현재 고려하는 부분 문자열의 길이를 조절하는 역할을 한다.

• cnt = 0이면 길이가 3짜리 (j = i + 2)
• cnt = 1이면 길이가 4짜리 (j = i + 3)
• cnt = 2이면 길이가 5짜리 (j = i + 4)

이후 m번의 질문마다 dp[s-1][e-1] 를 그대로 print해주면 된다. (인덱스값보다 1씩 큰 값이 대입됨)

 

 

정답코드

import sys
input = sys.stdin.readline
n = int(input())


nums = list(map(int,input().split()))

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 nums[i] == nums[i+1]:
        dp[i][i+1] = 1

#cnt + 3 = 현재 확인하는 부분 배열의 길이
for cnt in range(n-2):
    for i in range(n-2-cnt):
        #i가 현재 확인하는 부분배열의 시작점 j는 끝점
        j = i+2+cnt
        if nums[i] == nums[j] and dp[i+1][j-1] == 1:
            dp[i][j] = 1

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

 

 

 

덧붙이자면 input을 그대로 사용하면 시간초과가 난다... 이게 더 오래걸리는 건 알고있지만 정답이 잘 나오길래 그냥 썼었는데 앞으로 잘 변환해주어야겠다.