프로필사진

Go, Vantage point

가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.


Github | https://github.com/overnew/

Blog | https://everenew.tistory.com/





티스토리 뷰

반응형

문제

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

 

1509번: 팰린드롬 분할

세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하

www.acmicpc.net

 

풀이

일단 이전 단계인 문제 팰린드롬?을 풀고 오자.

 

이전 문제에서 우리는 start에서 end까지 팰린드롬을 이루는지의 여부를 is_palin[start][end]  저장해 문제를 해결하였다.

이번 문제에서도 해당 저장 값을 그대로 이용하자.

 

첫 글자(1)에서 현재 위치 (i)까지의 팰리드롬 개수의 최솟값을 dp[i]에 저장하자.

 

 i 번째 글자까지가 팰린드롬이지의 여부는 is_palin[1~i][i]를 확인해보면 된다.

 

is_palin[j+1][i]이 true인 경우

  j+1~i까지하나의 팰린드롬으로 묶어 1개의 분할을 얻는다.

 

그리고 1~j까지의 팰리드롬 분할 개수의 최솟값을 저장하는 dp[j]값을 1과 더해

 (j+1,i)를 팰린드롬 으로 묶을 때의 최솟값을 dp[j] +1로 얻을 수 있다.

 

이제 j를 0~i-1까지 순회하며 얻은 가장 작을 값이 dp[i]의 값이 된다.

따라서 dp[i] = min(dp[i], dp[j+1]+1) 이다.

 

참고로 문자열을 인덱스 1부터 시작하도록 변환하여

dp[0] = 0의 값을 미리 넣어두면

dp[2] = min(dp[2], dp[0]+1)과 같이 1~2를 하나의 팰린드롬으로 묶었을 때 이전의 글자가 더 없기 때문에, 계산이 용이해진다.

 

코드

반응형
댓글
반응형
인기글
Total
Today
Yesterday
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함