| 시간 제한 | 메모리 제한 |
| 2초 | 128MB |
문제
앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.
한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 길이 N(1 ≤ N ≤ 5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.
출력
첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.
풀이
하나하나 가능한 경우를 따져보며 최대 5000개 길이의 수열 arr을 팰린드롬으로 만들어보는 건 경우의 수가 너무나 많다. 하지만 어느 구간을 팰린드롬으로 만드는 비용을 구한다면 그 구간을 활용해 더 큰 구간의 팰린드롬을 만드는 비용을 얻을 수 있다.
이런 구간을 탐색한다고 해보자. i부터 j까지의 수열을 팰린드롬으로 만드는 최소 비용 dp[i][j]는 아래의 세 구간을 통해 얻을 수 있다. i~j 구간보다 작은 구간들의 최적해는 이미 구해진 상태인 것으로 생각하자. (이 가정을 반복하면 i == j인 i~j 구간의 해가 구해진 상태에서 시작하게 되는데, 이 값은 당연히 1개의 원소가 스스로 팰린드롬을 이루기 때문에 0이 된다.)
먼저 i~ j-1 구간의 최적해 dp[i][j-1]이 있다. 여기서 오른쪽에 j를 덧붙이며 arr[j]와 같은 값을 왼쪽에 하나 더하는 것으로 팰린드롬을 구성할 수 있다. 후보값은 dp[i][j-1] + 1이 된다. i+1~j 구간의 최적해를 이용한 후보값도 같은 방법으로 dp[i+1][j] + 1이 된다.
i+1~j-1 구간의 값은 약간 다른데, 만약 arr[i] == arr[j]인 경우는 dp[i+1][j-1]의 값에 새로운 원소 추가 없이 팰린드롬이 연장되므로 dp[i+1][j-1]의 값을 그대로 가져올 수 있다.
따라서 점화식을 이렇게 쓸 수 있다.
dp[i][j] = min(dp[i][j-1], dp[i+1][j]) + 1
if arr[i] == arr[j]:
dp[i][j] = min(dp[i][j], dp[i+1][j-1])
이 과정을 반복해 dp[0][-1]의 값을 출력하면 최적해를 얻을 수 있으나
파이썬은 메모리 초과가 뜬다. pypy3로 제출해서 가볍게 무시해주자.
dp테이블을 길이 N의 배열 두 개로 압축하는 테크닉으로 메모리를 절약할 수 있다. 원리만 간략하게 써보면, dp[3][8]을 구성하는데 dp[3][4]나 dp[3][5]같이 탐색 중인 구간보다 2칸 넘게 짧은 구간은 쓰이지 않으므로 버려도 된다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
N = int(input())
arr = list(map(int, input().split()))
dp = [0] * N
dp2 = [0] * N
for k in range(1, N):
i = N - k - 1
for j in range(N - 1, k - 1, -1):
dp2[j] = dp[j]
if arr[i] == arr[j]:
dp[j] = dp2[j - 1]
else:
dp[j] = min(dp[j], dp[j - 1]) + 1
i -= 1
print(dp[-1])
solution()
| 시간 제한 | 메모리 제한 |
| 2초 | 128MB |
문제
앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.
한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 길이 N(1 ≤ N ≤ 5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.
출력
첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.
풀이
하나하나 가능한 경우를 따져보며 최대 5000개 길이의 수열 arr을 팰린드롬으로 만들어보는 건 경우의 수가 너무나 많다. 하지만 어느 구간을 팰린드롬으로 만드는 비용을 구한다면 그 구간을 활용해 더 큰 구간의 팰린드롬을 만드는 비용을 얻을 수 있다.
이런 구간을 탐색한다고 해보자. i부터 j까지의 수열을 팰린드롬으로 만드는 최소 비용 dp[i][j]는 아래의 세 구간을 통해 얻을 수 있다. i~j 구간보다 작은 구간들의 최적해는 이미 구해진 상태인 것으로 생각하자. (이 가정을 반복하면 i == j인 i~j 구간의 해가 구해진 상태에서 시작하게 되는데, 이 값은 당연히 1개의 원소가 스스로 팰린드롬을 이루기 때문에 0이 된다.)
먼저 i~ j-1 구간의 최적해 dp[i][j-1]이 있다. 여기서 오른쪽에 j를 덧붙이며 arr[j]와 같은 값을 왼쪽에 하나 더하는 것으로 팰린드롬을 구성할 수 있다. 후보값은 dp[i][j-1] + 1이 된다. i+1~j 구간의 최적해를 이용한 후보값도 같은 방법으로 dp[i+1][j] + 1이 된다.
i+1~j-1 구간의 값은 약간 다른데, 만약 arr[i] == arr[j]인 경우는 dp[i+1][j-1]의 값에 새로운 원소 추가 없이 팰린드롬이 연장되므로 dp[i+1][j-1]의 값을 그대로 가져올 수 있다.
따라서 점화식을 이렇게 쓸 수 있다.
dp[i][j] = min(dp[i][j-1], dp[i+1][j]) + 1
if arr[i] == arr[j]:
dp[i][j] = min(dp[i][j], dp[i+1][j-1])
이 과정을 반복해 dp[0][-1]의 값을 출력하면 최적해를 얻을 수 있으나
파이썬은 메모리 초과가 뜬다. pypy3로 제출해서 가볍게 무시해주자.
dp테이블을 길이 N의 배열 두 개로 압축하는 테크닉으로 메모리를 절약할 수 있다. 원리만 간략하게 써보면, dp[3][8]을 구성하는데 dp[3][4]나 dp[3][5]같이 탐색 중인 구간보다 2칸 넘게 짧은 구간은 쓰이지 않으므로 버려도 된다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
N = int(input())
arr = list(map(int, input().split()))
dp = [0] * N
dp2 = [0] * N
for k in range(1, N):
i = N - k - 1
for j in range(N - 1, k - 1, -1):
dp2[j] = dp[j]
if arr[i] == arr[j]:
dp[j] = dp2[j - 1]
else:
dp[j] = min(dp[j], dp[j - 1]) + 1
i -= 1
print(dp[-1])
solution()
