| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (https://www.acmicpc.net/problem/10942#) | 256 MB | 54645 | 16199 | 11184 | 29.822% |
문제
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 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가 한 줄에 하나씩 주어진다.
출력
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
답안
import sys
lenNumbers = int(sys.stdin.readline())
numbers = [0] + list(map(int, sys.stdin.readline().split()))
lenQuestions = int(sys.stdin.readline())
questions = [tuple(map(int, sys.stdin.readline().split()))
for _ in range(lenQuestions)]
memo = [[False] * (lenNumbers+1) for _ in range(lenNumbers+1)]
for i in range(1, lenNumbers+1):
memo[i][i] = True
for i in range(1, lenNumbers):
if numbers[i] == numbers[i+1]:
memo[i][i+1] = True
def isPanlindrom(start, end):
return memo[start][end]
def slidingWindow():
for windowDelta in range(2, lenNumbers):
for start in range(lenNumbers-windowDelta+1):
end = start + windowDelta
if numbers[start] == numbers[end] and isPanlindrom(start+1, end-1):
memo[start][end] = True
def solve():
slidingWindow()
for question in questions:
start, end = question
print(1 if isPanlindrom(start, end) else 0)
solve()풀이
DP를 이용해 문제를 풀었다.
문제에서 주어진 시간이 넉넉하지 않아, 이전의 결과값을 재사용할 필요성이 있기 때문이었다.
내가 했던 DP 풀이에서 가장 핵심이 되는 부분은 다음과 같은 점화식이다.
어떠한 수열의 첫 번째 수와 마지막 수가 같고, 그 중간에 끼인 부분수열이 팬린드롬이면 그 수열은 팬린드롬이다.
이렇게 하면, window의 크기를 1, 2, 3, …, n으로 증가시켜나가면서 모든 질문 쌍에 대해 대답을 구할 수 있다.
memo에는 row번째부터 column번째까지의 부분수열이 팬린드롬인지 아닌지 여부를 저장한다.
처음에는 모두 False로 초기화한 뒤, window 크기를 증가시키며 이전 대답을 활용해 현재 질문에 대답한다.
첫 번째로 window 크기가 1인 경우이다.
이 경우에는 부분수열에 포함된 숫자가 하나뿐이고, 이것은 항상 팬린드롬이기 때문에 True를 저장한다.
for i in range(1, lenNumbers+1):
memo[i][i] = True그 다음으로는 window 크기가 2인 경우이다.
이 경우에는 부분수열에 포함된 숫자가 2개이므로, 두 개의 숫자의 값이 같으면 팬린드롬이라고 처리해주었다.
for i in range(1, lenNumbers):
if numbers[i] == numbers[i+1]:
memo[i][i+1] = True마지막으로 window 크기가 3 이상 n 이하인 경우이다.
위 점화식에서처럼, 수열의 첫 번째와 마지막 번째 수가 같고 그 끼인 부분수열이 팬린드롬이면 그 수열을 팬린드롬이라고 처리해주었다.
window 크기가 3 이상인 경우에는 window 크기가 1, 2, … 인 경우를 이용해 빠르게 판단할 수 있다.
for windowDelta in range(2, lenNumbers):
for start in range(lenNumbers-windowDelta+1):
end = start + windowDelta
if numbers[start] == numbers[end] and isPanlindrom(start+1, end-1):
memo[start][end] = True이렇게 모든 window 크기에 대해 팬린드롬인지 아닌지 판단하면, 모든 질문에 답할 수 있게 된다.
