팰린드롬?
오랜만에 dp 점화식을 제대로 찾은 문제였다. 중간에 반례를 검색해보긴 했지만, 굉장히 뿌듯한 문제들 중 하나였던 것 같다.🔥
칠판에 적힌 자연수 N개 중 S번째 부터 E번째 까지의 수가 팰린드롬을 이루는지 알아내는 문제이다.
시간 복잡도 향상을 위해 DP를 이용해야 하는데, 그림을 보며 이해해보자. 직접 시행착오를 겪으며 풀어나간 순서로 설명을 할 것이다.
- 먼저, DP 이차원 리스트를 다음과 같이 만들었다.
- 숫자의 길이가 1일 때는 항상 팰린드롬임으로 왼쪽 위 부터 오른쪽 아래까지 이어지는 대각선에는 주어진 값들을 집어넣고, 대각선 위쪽으로는 모두 0으로 초기화 해주었다.
- 이때, 탐색이 끝났는데 0인 값들은 팰린드롬을 이루지 않는 수들이라는 뜻으로 사용할 것이다.
- 대각선 아래쪽은 관심영역 밖이라 일단 빈칸으로 표시해 놓았다.
- 양옆의 숫자가 같고, 양옆의 숫자를 뺀 ‘2’가 팰린드롬이라면, 해당 숫자도 팰린드롬이라고 할 수 있다.
- ‘1 2 1’을 살펴보면, DP[1][1]이 0 이 아님으로 ‘2’는 팰린드롬이고, 1==1로 양옆의 숫자가 같음으로 ‘1 2 1’도 팰린드롬이라고 할 수 있다.
-
같은 방법으로 아래의 ‘1 3 1’, ‘1 2 1’도 팰린드롬이라고 할 수 있다.
- ‘2 1 3 1 2’를 살펴보면, DP[2][4]가 0이 아님으로 ‘1 3 1’은 펠린드롬이고, 양옆의 숫자가 2로 같음으로 ‘2 1 3 1 2’도 팰린드롬이다.
- 마찬가지 방법으로 ‘1 2 1 3 1 2 1’도 팰린드롬이다.
여기까지 생각하고, 코드로 구현해 제출했는데 틀렸다는 답이 돌아왔다.
이유는 숫자의 개수가 홀수인 경우는 위와 같이 모두 체크해 주었지만, 숫자의 개수가 짝수일 때를 생각하지 않았던 것이었다.
예를 들어 ‘2 2’도 팰린드롬을 이루는데 위의 방식에서는 이 경우가 체크되지 않는다. 아래의 그림을 살펴보자.
위에서는 해당 칸 바로 왼쪽 아래칸의 값이 0인지 아닌지로 양옆의 숫자를 뺀 값이 팰린드롬인지 아닌지를 판단했다. 하지만, 위의 방법으로 하면 이렇게 개수가 짝수인 경우에는 항상 팰린드롬이 아니라는 결과를 얻게된다. 그래서 해당 숫자를 넣어줬던 대각선 바로 아래 대각선 칸들에 1을 넣어주었다. ‘2 2’가 팰린드롬인지 판단 할 때, 양옆의 수를 뺀 값 ‘ ‘(빈칸)도 팰린드롬으로 치겠다는 의미로 받아들이면 된다.
이렇게 수정하면 ‘1 2 2 1 2 2 1’에서는 다음과 같은 DP리스트를 얻을 수 있다.
여기까지 완료했다면, S번째 부터 E번째 까지의 수가 팰린드롬을 이루는지 판단하는 것은 바로 할 수 있을 것이다.
CODE
import sys
read = sys.stdin.readline
n = int(read())
numbs = list(map(int, read().split()))
dp = list(list(0 for _ in range(n)) for _ in range(n))
for i in range(n):
dp[i][i] = 1
#길이가 짝수인 숫자들도 체크하기 위해 대각선 밑줄에도 1을 넣어준다.
if i+1 < n:
dp[i+1][i] = 1
# 해당 칸 행과 열에 해당하는 숫자가 같고,
# 해당 칸 왼쪽 아랫칸의 값이 0이 아니라면 팰린드롬이라고 할 수 있다.
for k in range(1, n):
for i in range(n-k):
x = i
y = i+k
#해당 칸 왼쪽아래의 DP값이 0이 아니다 = 그 칸에 해당하는 수는 팰린드롬을 이룬다.
#팰린드롬을 이루는 수의 양옆에 똑같은 수를 추가하면 그 수도 팰린드롬이다!
if dp[x+1][y-1] != 0 and numbs[x] == numbs[y]:
dp[x][y] = 1 #1을 넣어줌으로써 팰린드롬이라는 것을 저장해준다.
for _ in range(int(read())):
a, b = map(int, read().split())
if dp[a-1][b-1] == 0:
print(0)
else:
print(1)
[다시 풀어보기]