10942.팰린드롬?

D A S H B O A R D

Hyeon-Stone

D E V E L O P

S E C U R I T Y

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

문제 - 10942.팰린드롬?

성능 요약

메모리: 61956 KB, 시간: 2280 ms

분류

다이나믹 프로그래밍

문제 설명

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

먼저, 홍준이는 자연수 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가 한 줄에 하나씩 주어진다

첫 로직 : DP

import sys
input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
M = int(input())

question = [list(map(int, input().split())) for _ in range(M)]
palindromList = []

def palindrom(s,e):
    seq = sequence[s:e+1]
    if seq == seq[::-1]:
        return 1
    else:
        return 0

for q in question:
    print(palindrom(q[0]-1, q[1]-1))
Python
복사

•

이렇게 짤 경우 시간 복잡도가 O(NM)이 되기 때문에 시간 초과가 난다.

•

DP를 많이 해보지 않아서 도무지 갈피를 잡지 못해 검색…….

통과 로직

import sys
input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
dp = [[0]*N for _ in range(N)]
M = int(input())

for i in range(N):
    dp[i][i] = 1
for i in range(N-1):
    if sequence[i] == sequence[i+1]:
        dp[i][i+1] = 1
for i in range(2, N):
    for j in range(N-i):
        if sequence[j] == sequence[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = 1

for _ in range(M):
    a, b = map(int, input().split())
    print(dp[a-1][b-1])
Python
복사

•

생각을 해보면 1 ~ 5까지가 팰린드롬이라면, 2 ~ 4, 3 ~ 3 도 팰린드롬이다.
→ 여기까지는 생각을 했었는데 어떻게 저장하지 하다가 못풀었는데…… 

•

 즉, 2차원 배열에서 dp[1][5]가 필렌드롬인지 확인하기 위해서는 

◦

1번째와 5번째 숫자가 같은지 확인

◦

2 ~ 4까지의 수가 팰린드롬인지만 확인하면

◦

팰린드롬 여부를 알 수 있다.

Psuedo Code

•

dp[i][j]가 팰린드롬인가?

if 입력받은 List[i] == List[j]:

if dp[i+1][j-1] == 1:

dp[i][j]는 팰린드롬이다!

•

위의 로직을 실행시키기 위해서는 dp라는 2중 리스트를 구현해 채워넣어야 한다.
→ 예시로 설명

예시 - 문제에 있는 TestCase:

3 ~ 3과 같이 i == j 일 경우에는 항상 팰린드롬이다.

for i in range(N):
    dp[i][i] = 1
Python
복사

1~2와 같이 i와 i+1을 비교할 경우 2개의 숫자이기 때문에 i == i+1 이라면 팰린드롬이 성립된다.

for i in range(N-1):
    if sequence[i] == sequence[i+1]:
        dp[i][i+1] = 1
Python
복사

이제 3개 이상이 포함된 경우인데 이때는 위에서 말한것과 같이 i == j 일 때, i+1 ~ j-1까지가 팰린드롬이라면 i ~ j 도 팰린드롬이 성립한다.

for i in range(2, N):
    for j in range(N-i):
        if sequence[j] == sequence[j+i] and dp[j+1][j+i-1]:
            dp[j][j+i] = 1
Python
복사

•

3번 단계의 로직이 잘 이해가 안될 수 있어 예를 들어 설명하자면, 1 ~ 5 까지가 팰린드롬인지 판별하라.

◦

아직 1 ~ 5까지가 팰린드롬인지 모르는 상태이기 때문에 ? 표를 넣어주었다. 이는 dp[1][5]에 해당하는 값이다.

▪

이 때, i와 j가 모두 2로 i == j가 성립된다.

◦

다음으로 그럼 2~4까지가 팰린드롬인지 확인한다.

◦

dp[2][4]은 팰린드롬이기 때문에 dp[1][5]도 팰린드롬이 성립한다.

◦

박스가 채워지는 순서는 print찍어보면 알 수 있듯, [0][0]부터 대각선 아래로 내려가며 채워진다.

▪

0, 0 → 1, 1 →, 2, 2 …

▪

0, 1 → 1, 2 → 2, 3 …

▪

0, 2 → 1, 3 → 2, 4 …

▪

0, 3 → 1, 4 → 2, 5 … 