문제 설명
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 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을 출력한다.
틀린 코드 (5%)
import sys
n=int(sys.stdin.readline().rstrip())
arr=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
# dp 배열의 행은 arr의 시작 인덱스, 열은 arr의 끝 인덱스를 뜻한다.
# 시작 인덱스 > 끝 인덱스인 것은 성립할 수 없으므로 해당 영역은 사용하지 않는다.
dp=[[0]*n for _ in range(n)]
# 자신과 비교하면 항상 회문이므로 참
for i in range(n):
dp[i][i]=1
# o(n/2 * n/2)=> o(n^2)
for end_index in range(1,n):
for start_index in range(end_index-1):
if arr[start_index]==arr[end_index]:
dp[start_index][end_index]=dp[start_index+1][end_index-1]
else:
dp[start_index][end_index]=0
answer=[]
# o(m)
for _ in range(m):
s,e=list(map(int,sys.stdin.readline().split()))
answer.append(dp[s-1][e-1])
# 전체 시간 복잡도 == max(o(n^2),o(m))
for elem in answer:
print(elem)
틀린 코드의 경우 문자열의 길이가 2인 회문에 대해 처리가 안 되있다.
예를 들어 [2,2,3,3]이라는 배열에 대해 올바른 dp는 다음과 같다.
(참고로 dp의 경우 행은 위 배열의 s번째, 즉 시작 인덱스를 뜻하며 열은 위 배열의 e번 째, 즉 끝 인덱스를 뜻한다. 반드시 s<=e가 성립해야 하므로 s>e인 부분은 반드시 거짓이다. 따라서 다음 그림처럼 x처리를 했다.)
1 1 0 0
x 1 0 0
x x 1 1
x x x 1하지만 틀린 코드의 경우 다음과 같은 결과를 낸다.
1 0 0 0
x 1 0 0
x x 1 0
x x x 1정답 코드
import sys
n=int(sys.stdin.readline().rstrip())
arr=list(map(int,sys.stdin.readline().split()))
m=int(sys.stdin.readline().rstrip())
dp=[[0]*n for _ in range(n)]
for end_index in range(n):
for start_index in range(end_index+1):
# 시작과 끝이 같다면, 문자열 길이 1이므로 반드시 회문.
if start_index==end_index:
dp[start_index][end_index]=1
# 길이가 1을 초과하고, 시작과 끝 문자열이 동일하다면
elif arr[start_index]==arr[end_index]:
# 문자열 길이가 2라면 회문
if end_index-start_index==1:
dp[start_index][end_index]=1
# 그 외에는 시작과 끝 범위를 하나씩 줄여서 회문인지 확인.
else:
dp[start_index][end_index]=dp[start_index+1][end_index-1]
answer=[]
for _ in range(m):
s,e=list(map(int,sys.stdin.readline().split()))
answer.append(dp[s-1][e-1])
for elem in answer:
print(elem)해설
이 문제의 핵심은, 어떤 문자열 (start ~ end)가 회문일 경우 문자열 (start+1 ~ end-1) 역시 회문임을 이용한다. 작은 문제로 쪼갤 수 있고, 작은 문제의 답이 큰 문제의 답이 될 수 있으므로 dp에 해당한다.
이 문제의 dp 배열 의미를 다시 한번 설명하면 다음과 같다.
행은 배열의 s번째, 즉 시작 인덱스를 뜻하며 열은 배열의 e번 째, 즉 끝 인덱스를 뜻한다.
반드시 `s<=e`가 성립해야 하므로 `s>e`인 부분은 반드시 거짓이다. 입력 예시 1,2,1,3,1,2,1의 처리가 끝난 것을 전체적으로 보자.
1 0 1 0 0 0 1
x 1 0 0 0 1 0
x x 1 0 1 0 0
x x x 1 0 0 0
x x x x 1 0 1
x x x x x 1 0
x x x x x x 1여기서 dp[0][6]은 1213121을 뜻한다. 즉 0 ~ 6 번째까지의 문자다. 0번째와 6번째가 같으므로 회문인지 확인하기 위해 1 번째부터 5번째까지의 문자를 확인한다. 즉 dp[1][5] 인 21312를 본다. 여기도 같은 처리로 dp[2][4]인 131을 확인한다. 마지막으로 dp[3][3]인 1이 회문이다. 이를 거슬러 올라가면 dp[0][6]인 121321 역시 회문이다.
꽤 재귀와 같은 구조인데, 다른 풀이들을 참고하면 재귀 풀이도 있는 것 같다.
이 문제의 반복문 순서를 따라가면, 위와 같은 순서가 아니고 dp[3][3]->dp[2][4]->dp[1][5]->dp[0][6]의 순서로 계산이 된다.
(단, 시간 상 순서이며, ->은 값을 참고한다는 뜻이다.)
다시풀기 1회차
import sys
NOT = 0
PALINDROME = 1
n = int(input())
arr = list(map(int, sys.stdin.readline().split(' ')))
# 행은 시작, 열은 끝을 뜻한다.
dp = [[0] * n for _ in range(n)]
for col in range(n):
for row in range(col + 1):
if col - row == 0:
dp[row][col] = PALINDROME
elif col - row == 1:
if arr[row] == arr[col]:
dp[row][col] = PALINDROME
else:
if arr[row] == arr[col]:
dp[row][col] = dp[row + 1][col - 1]
m = int(input())
answer = []
for _ in range(m):
s, e = list(map(int, sys.stdin.readline().split()))
answer.append(dp[s - 1][e - 1])
for elem in answer:
print(elem)
