접근
- s 와 e 를 받아서 2차원 배열로 각각의 질문에 O(1) 에 답하는 것이 목표이다.
- 2000 X 2000 배열을 미리 초기화 한다면 초기화에 O(N ^ 2), 질문에 답하는 데 O(1) 이다.
- 점화식으로 top-down 으로 접근해서 풀었다. 이때 질문과 답하면서 배열을 조정한다.
- dp[s][e] 는 dp[s + 1][e - 1] 이 팰린드롬이라면 칠판배열[s] == 칠판배열[e] 에 따라 갈린다.
- 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)))
2등했다!
