[백준] 10942 팰린드롬? / DP / Python / 골4

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

 

부제: 시간초과와의 싸움

너무 정직하게 구현했더니 시간초과 뜸

질문에 따라 주어진 배열을 list[s:e+1]로 끊어서

그 배열을 for문 돌려서 팰린드롬인지 검증했는데, 이렇게 하니까 시간초과 뜸

dp를 쓰는 방법을 고민하자

 

<틀린풀이>

n = int(input())
l = list(map(int, input().split()))
l.insert(0,0)
m = int(input())
for i in range(m):
    s,e = map(int,input().split())
    temp = l[s:e+1]
    leng = len(temp)
    if leng==1:
        print(1)
        continue
    for j in range(leng//2):
        if temp[j]!=temp[leng-j-1]:
            print(0)
            break
    print(1)

 

 

dp문제니까 dp로 풀어야 된다

 

입력받은 문자열을 가로, 세로로 하는 2차원 배열로 한다

 

1. 문자열 길이가 1인 경우

dp[i][i]인 경우는 문자열 길이가 1인 경우인데, 이때는 무조건 팰린드롬이므로 1로 입력

 

2. 문자열 길이가 2인 경우

현재 원소와 그 다음 원소가 같은 경우만 팰린드롬임

 

3. 문자열 길이가 3 이상인 경우

이중 for문

- 바깥 for문에서 문자열 길이 지정

- 안쪽 for문에서 시작점 지정, 끝지점은 시작점+문자열길이-1

   - 시작과 끝 문자가 같고, 내부 구간이 팰린드롬인지 확인

   - dp[시작점][끝점] 값이 1이면 시작점-끝점으로 구성된 문자열이 팰린드롬인것이라서,

     시작점과 끝점을 제외한 내부 구간을 확인할 때는 dp[시작점-1][끝점+1] 값을 확인한다

 

dp를 다 구현하고 나서는

m개의 질의를 받고,

시작점과 끝점을 입력받을 때마다 dp[시작점][끝점] 값을 출력한다

 

 

그리고 이거 풀 때 input().split() 으로 입력 받으면 시간 초과 뜹니다

sys.stdin.readlin().split() 써야 시간 초과 안뜸

코드 구조의 문제인 줄 알았는데 입력 문제였음1!!!!!;;;