[백준] 10942 : 팰린드롬? (파이썬)

DP / 재귀+ Memorization 문제

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

 

접근 방식

• 재귀 + Memorization 기법을 활용하여 문제를 풀었다. 
  • 한 수열에 대해 질문의 개수가 M(1 ≤ M ≤ 1,000,000)번 주어진다. 질문의 개수가 들어올 때마다 재귀호출하여 값을 구하는 것은 매우 비효율적(반복됨)이다.
• 따라서, memo에 기록해둔 값이 있다면 dfs를 재귀호출하지 않고, memo에 기록해둔 값을 바로 리턴하도록 구현하였다.

 

💡 풀이코드 (성공)

import sys
sys.setrecursionlimit(10**9)

# 7
'''
1 -> [[1][-1][-1][-1][-1][-1][-1]] 1,2,3,4,5,6,7
2 -> [[1][-1][-1][-1][-1][-1]] 2,3,4,5,6,7
3 -> [[1][-1][-1][-1][-1]] 3,4,5,6,7
4 -> [[1][-1][-1][-1]] 4,5,6,7
5 -> [[1][-1][-1]]  5,6,7
6 -> [[1][-1]] 6,7 
7 -> [[1]] 7,7
'''

def palindrome(S, E):
    global n, m, memo, arr
    if S >= E or S < 0 or E < 0: return 1

    if memo[S][E - S] != -1:
        return memo[S][E - S]
    elif arr[S] == arr[E]:
        memo[S][E - S] = palindrome(S + 1, E - 1)
        return memo[S][E - S]
    else:
        memo[S][E - S] = 0
        return 0


n = int(sys.stdin.readline())
memo = [[-1] * (n - i) for i in range(n)]

arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
    memo[a - 1][b - a] = palindrome(a - 1, b - 1)
    print(memo[a - 1][b - a])
    # print(memo)

 

👩🏻‍💻 위의 코드

 

1.  memo 2차원 배열 생성

• 다음과 같은 형태의 memo 2차원 배열을 만들었다.

memo = [[-1] * (n - i) for i in range(n)]

 

• memo[S][E-S]에 S와 E가 겹치는지 안겹치는지 여부를 1 or 0으로 기록한다.
• n x n 형태의 2차원 배열이 아닌 위와 같이 2차원 배열을 만든 이유는 다음 예시를 들면서 설명하겠다.
• 다음은 n = 7일 때의 memo 2차원 배열의 초기화된 모습이다.
  두 정수 S와 E(1 ≤ S ≤ E ≤ N)가 이와 같음에 따라 S가 E보다 항상 작은 값임이 보장된다.
  따라서, S = 3일 때를 생각했을 때 E는 3보다 같거나 큰 값임이 항상 보장되므로 3보다 작은 값일 때의 경우를 기록할 필요가 없다.
  만약, 두 정수 S와 E(1 ≤ S ≤ E ≤ N)가 보장되지 않아 S = 3, E = 2 이러한 값이 나올 수 있다고 해도 이 값은 S = 2, E = 3일 때의 memo값을 참조하면 된다. 따라서, 중복되는 값이므로 값을 기록할 필요가 없다.

1 -> [[1][-1][-1][-1][-1][-1][-1]] 1,2,3,4,5,6,7
2 -> [[1][-1][-1][-1][-1][-1]] 2,3,4,5,6,7
3 -> [[1][-1][-1][-1][-1]] 3,4,5,6,7
4 -> [[1][-1][-1][-1]] 4,5,6,7
5 -> [[1][-1][-1]]  5,6,7
6 -> [[1][-1]] 6,7 
7 -> [[1]] 7,7

 

2. 주요 로직

• S >= E 라는 것은 팰린드롬이란 뜻이므로 1을 리턴한다.
• 만약 memo[S][E-S]에 기록해둔 값이 있다면, 해당 memo값을 리턴한다. (palindrome 재귀호출 X)
•  memo[S][E-S]에 기록해둔 값이 없는데, arr[S]와 arr[E] 값이 같다면 재귀 호출하고 결과를 memo에 기록한다.
•  memo[S][E-S]에 기록해둔 값이 없는데, arr[S]와 arr[E] 값이 다르다면 팰린드롬이 아니란 뜻이므로 곧바로 0을 리턴한다.

if S >= E or S < 0 or E < 0: return 1

if memo[S][E - S] != -1:
    return memo[S][E - S]
elif arr[S] == arr[E]:
    memo[S][E - S] = palindrome(S + 1, E - 1)
    return memo[S][E - S]
else:
    memo[S][E - S] = 0
    return 0