[BOJ] 1695 팰린드롬 만들기

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

 

 

한 수열이 주어졌을 때, 주어진 수열을 팰린드롬(palindrome, 회문)으로 만들기 위해 추가해야 하는 숫자의 최소 개수를 구하는 문제.

 

 

1/ 조건

1) 첫째 줄에 수열의 길이 n이 주어진다. 1 <= n <= 5000.

2) 수열을 이루는 숫자 n개가 주어진다. 각 숫자는 -2^31 이상 2^31 미만이다.

 

 

2/ 설계

숫자를 어떤 식으로 추가해야 짝을 맞출 수 있을까에 대해 고민하다가 숫자를 추가하는 것과 제거하는 것이 동등하다는 사실을 깨달았다. 재귀적으로 하나씩 제거한 결과가 회문인지를 검사하려고 했는데, 그 과정에서 중복된 결과가 얻어졌다. DP 문제라고 생각했다.

일단 top-down으로 풀어봤는데 메모리 초과가 났다. 재귀 횟수도 문제지만 메모이제이션과 숫자를 제거한 배열을 계속해서 만드는 게 문제인 듯했다. bottom-up으로 바꿔야겠다고 생각했다.

그런데 막상 바꾸려고 보니까 막막했다. '숫자를 하나 제거했을 때 그것이 회문인지를 판단하는 것'이 bottom-up에서는 어떤 방식으로 표현되어야 할까?

정답은 '부분 수열로부터 숫자를 하나 추가했을 때 그것이 회문인 경우와 회문이 아닌 경우에 대해 코드를 작성하는 것'이었다.

(연속적인) 부분 수열은 시작 인덱스와 종료 인덱스로 규정된다. dp[i][j]를 '시작 인덱스 i와 종료 인덱스 j인 부분 수열에서, 회문을 만들기 위해, 제거해야 하는 숫자의 최소 개수'라고 하자. numbers[i]와 numbers[j]가 같을 경우, dp[i][j]는 dp[i+1][j-1]과 똑같아야 한다. 다를 경우, dp[i][j]는 그보다 길이가 한 칸 짧은 부분 수열에 의존한다. 즉 dp[i+1][j]와 dp[i][j-1]에 의존하는데, numbers[i]나 numbers[j] 둘 중 하나는 제거해야 한다. 따라서 둘 중 더 적은 값에 1을 더해야 한다.

 

 

3/ 구현

def get_min_removal(series):
    dp = [[0]*n for _ in range(n)]

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i+length-1
            if series[i] == series[j]:
                dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

    return dp[0][n-1]


n = int(input())
numbers = [int(i) for i in input().split()]

print(get_min_removal(numbers))

 

O(n^2)의 시간복잡도를 갖는다. 불필요하게 함수로 분리한 건 top-down 방식으로 풀 때의 흔적이다.

 

 

4/ 결과

야호!

 

 

5/ 후기

1) 사실 위의 풀이는 한 번 제출했다가 메모리 초과로 포기했던 풀이였다. ChatGPT의 힘을 빌려서(ㅎㅎㅈㅅ) 임시 변수를 활용한 1차원 DP로 코드를 수정한 다음 제출해서 1차적으로 통과했었다. 그런데 그 이후 다른 사람들의 풀이를 살펴보는데 나랑 거의 똑같은 방식으로 푼 사람이 통과한 기록이 있었다. 차이점이 뭔가 하니 Python3가 아니라 PyPy3로 제출한 거였다. 혹시나 해서 내 코드를 PyPy3로 제출하니 통과했다. 세상에 이런 일이. 이제까지 PyPy3가 시간적으로 우월한 경우는 봤어도 메모리적으로 우월한 경우는 보지 못했는데, 아마 PyPy3에 책정된 메모리가 좀 더 너그러웠던 모양이다.

 

2) 다차원 DP에 대해 더 익숙해지고 싶은데 쉽지 않다. 그리고 container의 차원을 줄이는 게 어렵다. 0-1 knapsack 문제를 풀 때에는 1차원으로 쉽게 줄였던 것 같은데 이 문제의 경우에는 어떻게 해야 할지 감이 안 오더라. ChatGPT가 작성해준 코드는 이해했지만 내가 비슷한 문제에서 그와 같은 방법으로 차원을 줄일 수 있을까 하면 확신이 없다. 참고로 해당 코드는 아래와 같다:

def get_min_removal(series):
    dp = [0]*n

    for left in range(n-1, -1, -1):
        prev = 0
        for right in range(left, n):
            temp = dp[right]
            if series[left] == series[right]:
                dp[right] = prev
            else:
                dp[right] = min(dp[right], dp[right-1]) + 1
            prev = temp

    return dp[n-1]


n = int(input())
numbers = [int(i) for i in input().split()]

print(get_min_removal(numbers))

 

dp[right]에는 'rigth번째 숫자로 끝나는 부분 수열로부터 가장 긴 회문을 만들기 위해 제거해야 할 숫자의 개수'가 저장된다. 단, left는 n-1부터 점점 작아지도록 만들어야 한다. 본편의 풀이는 모든 연속적인 부분 수열에 대해서 생각하는 거였다면, 이 풀이는 길이가 k인 수열에서의 회문과 해당 수열에 숫자를 하나 더 붙여 길이가 (k+1)가 된 수열에서의 회문 사이의 관계를 보는 것이다.

 

3) 다시 보니까 설명이 난잡하다. 실제로 내 해결 과정도 난잡했다. 정확한 설계를 잡고 시작한 게 아니라 그때그때 보론을 덧대어 가며 완성한 여파다. '회문인 부분 수열 중 최대의 길이를 갖는 부분 수열'을 중점으로 코드를 작성했다면 훨씬 더 이해하기 쉬운 코드 및 설명이 되지 않았을까 싶다. 이건 결국 문제를 어떻게 해체하느냐, 어떤 단면으로 바라볼 것인가의 문제다. 일단 꾸역꾸역 끌고는 갔지만 컨디션이 좋아서 이렇게 된 거고, 만약 컨디션이 나빴다면 문제를 해결하지 못했을 것 같다. 컨디션과 무관하게 문제를 풀 줄 알아야 한다. 그러려면 역시 설계가 중요하다. 설계는 어떻게 해야 잘할 수 있을까? 앞에서 말한 것처럼 '단면'을 잘 설정해야 하는데, 그러려면 문제 해결 측면에서 동등한 방식에 어떤 것들이 있는지, 혹은 이 문제를 관통하는 개념이 무엇인지를 잘 정의해야 할 것 같긴 하지만… 역시 체계적인 방법이 무엇인가 하면 잘 모르겠다. 당장은 계속해서 시야를 넓히는 수밖에.