10942번: 팰린드롬?
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
www.acmicpc.net
문제
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.
먼저, 홍준이는 자연수 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
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
dp = [[0 for _ in range(n)] for _ in range(n)]
# 길이가 1
for i in range(n):
dp[i][i] = 1
# 길이가 2
for i in range(1, n):
if arr[i-1] == arr[i]:
dp[i-1][i] = 1
# 길이가 3 이상
for i in range(2, n):
for j in range(2, i+1): # 문자열 길이
if arr[i] == arr[i-j] and dp[i-j+1][i-1] == 1:
dp[i-j][i] = 1
m = int(input())
for _ in range(m):
s, e = map(int, input().split())
print(dp[s-1][e-1])
s, e번째 수가 팰린드롬을 이룬다면 dp 배열에 1을 저장하고 아니라면 0을 저장한다.
팰린드롬의 길이가 1, 2, 3 이상인 경우를 따로 구한다.
1, 2인 경우는 간단하니 설명하지 않는다.
3 이상인 경우, 양끝의 숫자가 같고 그 사이가 팰린드롬을 이루는지 확인해본다. 이때 팰린드롬을 이루는지 확인은 이미 dp 배열에 저장된 값들로 할 수 있다.
처음에는 아래와 같이 dp 배열에 집합을 넣어서 풀어보려 했다.
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr_length = len(arr)
dp = [set([i]) for i in range(arr_length)]
for i in range(1, arr_length):
for j in dp[i-1]:
if j == 0:
if i == 1 and arr[0] == arr[1]:
dp[i].add(j)
else:
continue
if arr[j-1] == arr[i]:
dp[i].add(j-1)
m = int(input())
for _ in range(m):
s, e = map(int, input().split())
if s-1 in dp[e-1]:
print(1)
else:
print(0)
틀린 코드이지만 어떻게 하려고 한건지 설명을 해보자면
- 집합을 원소로 갖는 dp 배열을 만든다. s, e번째 인덱스까지 팰린드롬이 만들어진다고 하면 e번째 인덱스의 원소인 집합에는 s 값들이 들어간다. 배열을 생성할 때 길이가 1인 경우도 팰린드롬이므로 자기자신의 인덱스는 기본으로 갖도록 만든다.
- 이제 dp 배열을 하나씩 살펴보며 업데이트해줄 것이다
- dp[i-1]에는 j부터 i-1까지 팰린드롬이 되는 인덱스들(j)이 저장되어있을 것이다. 이 인덱스의 한 칸 이전의 인덱스의 arr이 현재 arr[i]와 같다면 중간이 팰린드롬을 이루고 양끝도 같다는 것이므로 j-1번째를 dp[i]에 추가해줄 수 있다.
- dp[e-1]에 s-1이 존재한다면 팰린드롬을 이루는 것이므로 1을 출력해준다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 7579번 앱 (0) | 2022.09.29 |
---|---|
[Python/파이썬] 백준 11066번 파일 합치기 (1) | 2022.09.24 |
[Python/파이썬] 백준 2342번 Dance Dance Revolution (0) | 2022.09.09 |
[Python/파이썬] 백준 17404번 RGB거리 2 (0) | 2022.08.29 |
[Python] 백준 11054번 가장 긴 바이토닉 부분 수열 (0) | 2022.07.21 |