출처
Koreatech OnlineJudge(링크)
문제이해
5000자 이하의 문자가 입력으로 주어지고, 임의의 위치에 문자를 추가하여 펠린드롬으로 만들 때 추가하는 문자의 개수를 최소화하면, 몇 개인지를 구하는 문제이다.
문제접근
동적 프로그래밍 문제이다.
인덱스 a부터 인덱스 b까지의 구역에 대해 펠린드롬을 만들기 위한 최소비용을 D[a][b]라고 하자. D[a][b]를 한 단계 작은 계산결과로 구하기 위해 두 가지 조건을 따져봐야 한다.
1. 구역의 맨 앞과 맨 뒤가 같은 문자인 경우
D[a][b] (구역의 전체)는 D[a+1][b-1] (회색 부분)와 같다.
2. 구역의 맨 앞과 맨 뒤가 다른 문자인 경우
D[a][b] = 1+min(D[a][b-1], D[a+1][b])
a부터 b-1까지의 부분구역과, a+1부터 b까지의 부분구역 중에서 비용이 작은 것을 선택하여 거기에 1을 더한 값을 D[a][b]로 한다.
Top-down 방식으로 점화식을 해결하면 시간복잡도가 지수함수가 되므로, 아래에서부터 누적하여 구해야 한다.
구간의 길이를 1부터 전체까지 늘려 가며 데이터를 얻는 것이다.
전에 포스팅했던 이 문제와 같은 아이디어이다.
구현
다음과 같이 전처리하면 복잡하지 않게 반복문을 짤 수 있다.
- 구간의 길이가 1인 경우 D값은 0으로 한다.
- 구간의 길이가 2인 경우 D값은, 두 문자가 같을 때 0, 다를 때 1로 한다.
코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1060/1060.cpp