문제 - 10942.팰린드롬?
성능 요약
메모리: 61956 KB, 시간: 2280 ms
분류
다이나믹 프로그래밍
문제 설명
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.
각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다
예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
•
S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
•
S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
•
S = 3, E = 3인 경우 1은 팰린드롬이다.
•
S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다
둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.
셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.
넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다
첫 로직 : DP
import sys
input = sys.stdin.readline
N = int(input())
sequence = list(map(int, input().split()))
M = int(input())
question = [list(map(int, input().split())) for _ in range(M)]
palindromList = []
def palindrom(s,e):
seq = sequence[s:e+1]
if seq == seq[::-1]:
return 1
else:
return 0
for q in question:
print(palindrom(q[0]-1, q[1]-1))
Python
복사
•
이렇게 짤 경우 시간 복잡도가 O(NM)이 되기 때문에 시간 초과가 난다.
•
DP를 많이 해보지 않아서 도무지 갈피를 잡지 못해 검색…….
통과 로직
import sys
input = sys.stdin.readline
N = int(input())
sequence = list(map(int, input().split()))
dp = [[0]*N for _ in range(N)]
M = int(input())
for i in range(N):
dp[i][i] = 1
for i in range(N-1):
if sequence[i] == sequence[i+1]:
dp[i][i+1] = 1
for i in range(2, N):
for j in range(N-i):
if sequence[j] == sequence[j+i] and dp[j+1][j+i-1]:
dp[j][j+i] = 1
for _ in range(M):
a, b = map(int, input().split())
print(dp[a-1][b-1])
Python
복사
•
생각을 해보면 1 ~ 5까지가 팰린드롬이라면, 2 ~ 4, 3 ~ 3 도 팰린드롬이다.
→ 여기까지는 생각을 했었는데 어떻게 저장하지 하다가 못풀었는데…… ![](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)
•
즉, 2차원 배열에서 dp[1][5]가 필렌드롬인지 확인하기 위해서는
◦
1번째와 5번째 숫자가 같은지 확인
◦
2 ~ 4까지의 수가 팰린드롬인지만 확인하면
◦
팰린드롬 여부를 알 수 있다.
Psuedo Code
•
dp[i][j]가 팰린드롬인가?
if 입력받은 List[i] == List[j]:
if dp[i+1][j-1] == 1:
dp[i][j]는 팰린드롬이다!
•
위의 로직을 실행시키기 위해서는 dp라는 2중 리스트를 구현해 채워넣어야 한다.
→ 예시로 설명
예시 - 문제에 있는 TestCase:
1.
3 ~ 3과 같이 i == j 일 경우에는 항상 팰린드롬이다.
for i in range(N):
dp[i][i] = 1
Python
복사
2.
1~2와 같이 i와 i+1을 비교할 경우 2개의 숫자이기 때문에 i == i+1 이라면 팰린드롬이 성립된다.
for i in range(N-1):
if sequence[i] == sequence[i+1]:
dp[i][i+1] = 1
Python
복사
3.
이제 3개 이상이 포함된 경우인데 이때는 위에서 말한것과 같이 i == j 일 때, i+1 ~ j-1까지가 팰린드롬이라면 i ~ j 도 팰린드롬이 성립한다.
for i in range(2, N):
for j in range(N-i):
if sequence[j] == sequence[j+i] and dp[j+1][j+i-1]:
dp[j][j+i] = 1
Python
복사
•
3번 단계의 로직이 잘 이해가 안될 수 있어 예를 들어 설명하자면, 1 ~ 5 까지가 팰린드롬인지 판별하라.
◦
아직 1 ~ 5까지가 팰린드롬인지 모르는 상태이기 때문에 ? 표를 넣어주었다. 이는 dp[1][5]에 해당하는 값이다.
▪
이 때, i와 j가 모두 2로 i == j가 성립된다.
◦
다음으로 그럼 2~4까지가 팰린드롬인지 확인한다.
◦
dp[2][4]은 팰린드롬이기 때문에 dp[1][5]도 팰린드롬이 성립한다.
◦
박스가 채워지는 순서는 print찍어보면 알 수 있듯, [0][0]부터 대각선 아래로 내려가며 채워진다.
▪
0, 0 → 1, 1 →, 2, 2 …
▪
0, 1 → 1, 2 → 2, 3 …
▪
0, 2 → 1, 3 → 2, 4 …
▪
0, 3 → 1, 4 → 2, 5 …