백준 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을 출력한다.

 

 

해결과정

해당 문제를 해결하기 위해선 동적프로그래밍을 다룰 필요가 있었다. Dp의 방식으로 top_down , bottom_up 의 방식이 존재하지만, 해당 방식은 두 가지 방식 모두 해결할 수 있었다. 

두 방식 모두 공통적으로 내포하고 있는 바가 있다. 그것은 이전 상태에 따라 현 상태가 결정된다는 것이다.

 

 

 

1. Top_down

Top down 방식으로 해결하기 위해  Recursion 방식을 취하였다. 

Recursion은 의외로 시간복잡도가 높다. for문과 같은 시간복잡도를 가진다 O(n) 따라서 시간초과를 해결하기엔 효율적인 코드는 아니다. 

 

핵심은 n 이 1일때, 2일때, 3이상일때를 잘 구분하는 것이다. 

즉 이미지상으로 설명하자면 중간부터 검색하여 점점 넓혀 가는 것이다.

 

다음은 해당 코드이다

 

def dynamic(number,lst):
    if len(lst) == 1:
        return 1
    elif len(lst) ==2:

        if number[lst[0]-1] == number[lst[1] - 1]:
            return 1
        else:
            return 0

    if number[lst[0]-1] != number[lst[-1] - 1]:

        return 0
    else:
        lst = lst[1:-1]
        return dynamic(number,lst)

n = int(input())
number = list(map(int,input().split()))
k = int(input())
lst = []
for k in range(k):
    a = list(map(int, input().split()))
    lst.append(a)

for l in lst:
    print(dynamic(n,number,l))

2. bottom-up 방식

bottom-up 방식은 각 start end 에 해당하는 배열을 생성, 이를 모두 계산하고 난 뒤 해당 지점을 print 하는 방식을 취하였다. 

해당 방식도 recursion과 비슷하다. 안에서부터 검사하면서 나온다는 점, 이전 값을 인지 하여야 뒷 값을 계산할 수 있다는 점이 그렇다. 

import sys
input = sys.stdin.readline

n = int(input())
number = list(map(int,input().split()))
k = int(input())
lst = []
for k in range(k):
    a = list(map(int, input().split()))
    lst.append(a)


l = [[0]*n for k in range(n)]

for i in range(n):

    for start in range(n):
        end = start + i
        if end >= n:
            break;
        if start == end:
            l[start][end] = 1
            continue
        elif start +1 == end:
            if number[start] == number[end]:
                l[start][end] = 1
                continue
        elif start < end:
            if number[start] == number[end] and l[start+1][end-1]==1:
                l[start][end] = 1

for k in lst:
    print(l[k[0]-1][k[1]-1])