BOJ 10942: 팰린드롬? [Python 3]

개강 기념으로 블로그를 업데이트 해보려고 한다.

 시간 제한이 까다로운 문제이고, DP를 통해서 해결했다.

import sys
input=sys.stdin.readline
n=int(input())
ndata=list(map(int,input().split()))
m=int(input())
mdata=list(list(map(int,input().split())) for _ in range(m))
dp=[[0 for _ in range(n)] for _ in range(n)]
for index in range(n):
    for start in range(n):
        end=start+index
        if end>=n:
            break
        if start==end:
            dp[start][end]=1
            continue
        if end==start+1 and ndata[start]==ndata[end]:
            dp[start][end]=1
            continue
        if ndata[start]==ndata[end] and dp[start+1][end-1]:
            dp[start][end]=1
for i in range(m):
    a,b=mdata[i]
    print(dp[a-1][b-1])

풀이는 해당 표로 보이려고 한다.

모든 케이스를 담을 dp라는 데이터를 만들려고 한다.

먼저, 이중 for문 안에 있는 4개의  if문들을 각각 1번, 2번, 3번, 4번 케이스라고 명명하겠다.

1번 케이스는 끝점의 좌표가 해당 테이블을 벗어날 때다. 계산 불가이므로 다음 행으로 넘어간다.

2번 케이스는 첫 좌표와 마지막 좌표가 같을 때, 즉 하나의 수에 대해 계산할 때이다. (노랑색 선)

3번 케이스는 두개의 연속된 좌표를 확인할 때이다. 해당 문제에는 가능한 식이 없으나, 만약 22같이 두개의 숫자가 같으면, 이 케이스를 만족시킨다.

마지막 4번 케이스는 3이상의 길이를 가진 문자열을 확인할 때 쓰인다.

맨 처음 수와 뒷 수가 같고, 맨 처음 수의 뒷 수, 맨 뒷 수의 앞 수가 케이스를 만족하는지 확인하면, 만족한다. (보라색 선)