[Python] 백준 1695 - 팰린드롬 만들기

https://www.acmicpc.net/problem/1695

 

문제

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다.

한 수열이 주어졌을 때, 이 수열에 최소 개수의 수를 끼워 넣어 팰린드롬을 만들려고 한다. 최소 몇 개의 수를 끼워 넣으면 되는지를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 N(1≤N≤5,000)이 주어진다. 다음 줄에는 N개의 수열을 이루는 수들이 주어진다. 각 수들은 int 범위이다.

출력

첫째 줄에 끼워 넣을 수들의 최소 개수를 출력한다.

 

---

풀이

dp 문제이다.

dp 문제라면 본디, 하나의 큰 문제를 작은 여러 개의 문제로 쪼개 소문제를 풀고 그 값을 저장하고, 재이용하는 것이라고 배웠다.

이 문제는 어떻게 문제를 작은 문제들로 쪼갤 수 있을까?

---

IDEA

예를 들어, 주어진 예제인 1 2 3 4 2 를 보자.

1 2 3 4 2는 팰린드롬이 아니다. 당장 맨 끝과 처음만 봐도 숫자가 다르기 때문이다. 크게 봤을 때 이 문자열을 팰린드롬으로 맞춰주려면, 맨 앞에 2가 들어가거나 맨 뒤에 1이 들어가야 할 것이다.

 

맨 뒤에 1이 들어갔다고 가정하자(실제로 이게 올바른 방법이다).

 

그러면 우리는 맨 앞과 맨 끝을 제외하고, 그 내부 알맹이인 2 3 4 2만 보면 될 것이다.

 

그러면 2 3 4 2의 경우는 맨 앞과 끝이 같다. 그래서 우리는 그 내부 알맹이인 3 4만 보면 된다.

 

3 4의 경우에는 길이가 2이다. 4 3 4를 하든 3 4 3을 하든 상관은 없고, 둘 다 추가해야하는 숫자의 개수는 1이다.

 

---

이런 아이디어로 재귀함수든 반복문이든 짜면 될 것이다.

 

먼저 이 아이디어를 그대로 재귀함수 형식으로 짜고, 인덱스 x부터 y까지에 대해서 풀이한 값을 2차원 dp에 저장해놓았다.

다음은 그 코드이다.

 

import sys
sys.setrecursionlimit(10000)
N = int(input())
arr = list(map(int, input().split()))

#sol(x, y)의 값을 dp[x][y]에 저장함(x부터 y까지)
dp = [[-1]*N for _ in range(N)]

def sol(x, y):
    if dp[x][y] != -1:
        return dp[x][y]

    if x == y:
        dp[x][y] = 0
        return 0
    if x+1 == y:
        if arr[x] == arr[y]:
            dp[x][y] = 0
            return 0
        else:
            dp[x][y] = 1
            return 1
    if arr[x] == arr[y]:
        dp[x][y] = sol(x+1, y-1)
        return dp[x][y]
    else:
        dp[x][y] = min(sol(x+1, y), sol(x, y-1)) + 1
        return dp[x][y]

print(sol(0, N-1))

 

틀린 코드는 아닐 것이다(아마). 그런데 예상과는 다르게 맨 처음부터 메모리 초과가 났다.

 

아마 재귀함수를 써서 그런가보다. 어쩔 수 없이 코드를 반복문으로 바꿔야겠다.

 

그런데, 코드를 반복문으로 바꾸러면 dp 배열의 개념을 살짝 바꿔야한다.

인덱스 x부터 y까지의 소문제 정답을 dp에 저장하는 것이 아니라, 길이가 l이고 인덱스가 x부터 시작하는 dp를 저장해야한다.

 

그 이유인 즉슨, 

 

결국에는 dp에 저장되는 값은 길이가 1 또는 2인 가장 짧은 부분들이기 때문에 길이가 짧은 순서대로 dp 값을 저장해나가야 할 것이다.

그래서 x, y의 인덱스로 관리하는 것보다는 길이별로 관리하는 것이 반복문을 쓰기 좋을 것이다.

 

다음은 이를 고려하여 완전히 수정한 코드이다.

 

N = int(input())
arr = list(map(int, input().split()))

dp = [[-1]*N for _ in range(N)]


for l in range(N):
    for x in range(N-l):
        if l == 0:
            dp[l][x] = 0
        elif l == 1:
            if arr[x] == arr[x+l]:
                dp[l][x] = 0
            else:
                dp[l][x] = 1
        else:
            if arr[x] == arr[x+l]:
                dp[l][x] = dp[l-2][x+1]
            else:
                dp[l][x] = min(dp[l-1][x], dp[l-1][x+1]) + 1

print(dp[-1][0])

 

오늘 배운 교훈이 있다:

dp를 짤 때 재귀를 하면 소문제가 무엇인지, 무엇을 의도한 코드인지 확실히 잘 알 수 있다. 다만 시간이 느리고 메모리를 많이 잡아먹는다.

그래서 dp를 짤 때는 주로 반복문을 쓰는데, 아쉽게도 반복문은 빠르고 효율도 좋지만 문제 풀이를 할 때 어떻게 푼 것인지, 코드의 의도가 무엇인지 해석하기 좀 어렵다라는 단점이 있다.

 

젠장