동주의 세상

Clean and minimal personal blog

백준 10942 팰린드롬? - 파이썬

Posted at — Jun 26, 2021

접근

  1. s 와 e 를 받아서 2차원 배열로 각각의 질문에 O(1) 에 답하는 것이 목표이다.
  2. 2000 X 2000 배열을 미리 초기화 한다면 초기화에 O(N ^ 2), 질문에 답하는 데 O(1) 이다.
  3. 점화식으로 top-down 으로 접근해서 풀었다. 이때 질문과 답하면서 배열을 조정한다.
  4. dp[s][e] 는 dp[s + 1][e - 1] 이 팰린드롬이라면 칠판배열[s] == 칠판배열[e] 에 따라 갈린다.
  5. base case 는 s == e 와 s == e - 1 인 경우 (s + 1, e - 1을 조회할 수 없기 때문에) 로 뒀다.

사고

이렇게 대놓고 배열로 풀어주세요 하는 건 어느정도 익숙하다. DP 중에 무엇을 메모이제이션해야 할 지 감이 안 오는 문제들이 훨씬 어려운 것 같다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
m = [0] + list(map(int, input().split()))

Q = int(input())

dp = [[-1 for j in range(N + 1)] for i in range(N + 1)]

def getDP(s, e):
    if dp[s][e] == -1:
        if s == e:
            dp[s][e] = 1
        elif s == e - 1:
            dp[s][e] = 1 if m[s] == m[e] else 0
        else:
            prev = getDP(s + 1, e - 1)
            if prev == 1:
                dp[s][e] = 1 if m[s] == m[e] else 0
            else:
                dp[s][e] = 0
    return dp[s][e]

ans = [0] * Q
for i in range(Q):
    s, e = map(int, input().strip().split())
    ans[i] = getDP(s, e)

sys.stdout.write('\n'.join(map(str, ans)))

submission

 

2등했다!

record