왜 DP?
개인적으로 왜 동적 프로그래밍 문제인지를 이해하는 것이 어려웠다. 하지만 왜 DP 문제인지만 이해하니 문제는 비교적 간단했던 것 같다.
위 그림처럼 start 부터 end까지의 문자열이 팰린드롬인지 확인하려고 할 때, 문자열 [start+1,end-1]이 팰린드롬이라는 사실을 이미 알고 있다면 문자열 전체를 검사할 필요 없이 앞 뒤 두 글자 start와 end만 비교해보면 된다.
즉, 어떤 문자열이 팰린드롬인지 확인하려면 양 끝의 문자가 같은지를 확인하고 양 끝단을 제외한 문자열이 팰린드롬인지 확인하면 된다.
따라서, 어떤 문자열이 팰린드롬인지를 판단하는 과정은 다음과 같다.
- 양 끝의 문자가 다르면 -> 팰린드롬 아님
- 양 끝의 문자가 같을 때, 가운데 문자열이
- 팰린드롬이라면 -> 팰린드롬
- 팰린드롬이 아니라면 -> 팰린드롬 아님 - 가운데 문자열이 팰린드롬인지 아닌지 모른다면 알 때까지 문자열의 길이를 앞뒤로 하나씩 줄이면서 위의 과정을 반복한다.
가운데 문자열이 팰린드롬인지 아닌지 아는 문자열이 나올때까지 문자열의 범위를 줄여가면서 같은 과정을 계속 반복한다는 점에서 DP 문제라고 할 수 있다!
문제 접근하기
먼저 문자열에서 i 번째 글자부터 j번째 글자까지 떼어낸 부분문자열이 팰린드롬인지 아닌지를 저장하는 배열 dp[i][j] 를 만든다.
아래의 과정을 통해 dp 테이블을 채워 나간다.
- 문자열의 양끝을 비교한다.
1.1 문자열의 양 끝이 같다면 가운데 문자열이 팰린드롬인지 확인한다.
- 팰린드롬이라면 -> return True
- 팰린드롬이 아니라면 -> return False
1.2 문자열의 양 끝이 다르다면 --> return False
코드로 구현하기
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])
for문의 범위 지정은 어떻게?
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번-팰린드롬-파이썬
