개인적으로 왜 동적 프로그래밍 문제인지를 이해하는 것이 어려웠다. 하지만 왜 DP 문제인지만 이해하니 문제는 비교적 간단했던 것 같다.
위 그림처럼 start 부터 end까지의 문자열이 팰린드롬인지 확인하려고 할 때, 문자열 [start+1,end-1]이 팰린드롬이라는 사실을 이미 알고 있다면 문자열 전체를 검사할 필요 없이 앞 뒤 두 글자 start와 end만 비교해보면 된다.
즉, 어떤 문자열이 팰린드롬인지 확인하려면 양 끝의 문자가 같은지를 확인하고 양 끝단을 제외한 문자열이 팰린드롬인지 확인하면 된다.
따라서, 어떤 문자열이 팰린드롬인지를 판단하는 과정은 다음과 같다.
가운데 문자열이 팰린드롬인지 아닌지 아는 문자열이 나올때까지 문자열의 범위를 줄여가면서 같은 과정을 계속 반복한다는 점에서 DP 문제라고 할 수 있다!
먼저 문자열에서 i 번째 글자부터 j번째 글자까지 떼어낸 부분문자열이 팰린드롬인지 아닌지를 저장하는 배열 dp[i][j]
를 만든다.
아래의 과정을 통해 dp 테이블을 채워 나간다.
import sys
input = sys.stdin.readline
n = int(input())
numbers = list(map(int, input().split()))
m = int(input())
#dp
dp = [[0] * n for _ in range(n)]
for num_len in range(n):
for start in range(n - num_len):
end = start + num_len
# 시작점과 끝점이 같다면 글자수가 1개이므로 무조건 팰린드롬
if start == end:
dp[start][end] = 1
# 시작점의 글자와 끝점의 글자가 같다면
elif numbers[start] == numbers[end]:
# 두 글자짜리 문자열이라면 무조건 팰린드롬
if start + 1 == end: dp[start][end] = 1
# 가운데 문자열이 팰린드롬이라면 팰린드롬
elif dp[start+1][end-1] == 1: dp[start][end] = 1
#정답출력하기
for question in range(m):
s, e = map(int, input().split())
print(dp[s-1][e-1])
dp 테이블을 채우기 위해 2중 for 문을 그대로 돌렸더니 아래 그림 왼쪽과 같은 현상이 발생했다!
예) 문자열 [1,4]를 검사하기 위해서 문자열 [2,3]이 팰린드롬인지 확인해야 하는데, 아직 dp 테이블이 채워져 있지 않아서 제대로 된 결과를 얻을 수 없다.
따라서 dp 테이블을 채워나가는 순서를 오른쪽 그림과 같은 순서대로 채워나가야 한다. 이 같은 순서대로 테이블을 채워나가기 위한 2중 for 문은 아래와 같다.
for num_len in range(n):
for start in range(n - num_len):
end = start + num_len
참고한 블로그:
https://chocochip101.tistory.com/entry/백준-10942번-팰린드롬-파이썬