[다이나믹 프로그래밍] 백준 1509번 : 팰린드롬 분할 / 골드 1

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

1509번: 팰린드롬 분할

text = input()
n = len(text)

table = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
    table[i][i] = True

for i in range(n-1):
    if text[i] == text[i+1]:
        table[i][i+1] = True

## 대각선 방향으로 채워줘야 함
for t in range(n-2):
    for i in range(n-2-t):
        j = i + t + 2
        if text[i] == text[j] and table[i + 1][j - 1]:
            table[i][j] = True

## dp
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(1, n):
    min_val = dp[i-1]+1
    for j in range(i):
        if table[j][i]:
            min_val = min(min_val, dp[j-1] + 1)
    dp[i] = min_val
print(dp[-1])

어려운 문제라서 굉장히 오래걸렸다;;

내가 푼 방식에서는 2개의 자료 구조가 등장한다. table과 dp.

2차원 배열 table의 (i, j) 성분은 text[i]부터 text[j]까지의 부분 문자열이 팰린드롬인지에 대한 여부를 bool타입으로 담고 있다.

1차원 배열 dp는 이 table을 활용하여 답을 구해낸다.

 

 

- table을 구하는 방식

처음엔 아래와 같이 구현했다. 이 방법은 시간 초과가 난다. 팰린드롬 여부를 판단하는 과정에서 중복을 걸러내지 않고 무식하게 판단하였기 때문이다. part == part[::-1]에서 O(n)시간이 소요되기 때문에 이 부분을 고치는 것이 핵심이다.

table = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i, n):
        part = text[i:j+1]
        if part == part[::-1]:
            table[i][j] = True

그럼 어떻게 table을 빨리 만들 수 있을까?

아래와 같이 개선했다.

table = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
    table[i][i] = True

for i in range(n-1):
    if text[i] == text[i+1]:
        table[i][i+1] = True

## 대각선 방향으로 채워줘야 함
for t in range(n-2):
    for i in range(n-2-t):
        j = i + t + 2
        if text[i] == text[j] and table[i + 1][j - 1]:
            table[i][j] = True

 

 

- dp 리스트로 답 구하기

## dp
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(1, n):
    min_val = dp[i-1]+1
    for j in range(i):
        if table[j][i]:
            min_val = min(min_val, dp[j-1] + 1)
    dp[i] = min_val
print(dp[-1])