문제 이해하기
소문자로만 구성된 문자열 s와 정수 k가 주어집니다. 우리는 다음 두 가지 작업을 순서대로 수행해야 합니다.
- 필요하다면 문자열 s의 일부 문자를 다른 소문자 영어 알파벳으로 변경합니다.
- 그다음 문자열 s를 정확히 k개의 부분 문자열로 분할하되, 각 부분 문자열이 모두 회문(palindrome)이 되도록 만듭니다.
최종 목표는 이러한 분할을 달성하기 위해 변경해야 하는 문자의 최소 개수를 구하는 것입니다.
예시
문자열이 "ababbc"이고 k = 2라고 가정해 보겠습니다. 이 경우 답은 1입니다. 두 개의 회문으로 나누기 위해 단 한 글자만 변경하면 되기 때문입니다. 예를 들어 마지막 'c'를 'b'로 바꾸면 "bbb", 또는 뒤에서 두 번째 'b'를 'c'로 바꾸면 "cbc"라는 회문을 만들 수 있고, 나머지 부분 "aba" 역시 회문이 됩니다.
접근 방법: 동적 계획법과 메모이제이션
이 문제는 두 단계의 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 먼저 모든 구간에 대해 회문으로 만들기 위한 최소 변경 비용을 사전에 계산하고, 이후 재귀 함수와 메모이제이션을 활용해 전체 문자열을 k개의 구간으로 나누는 최적의 분할 지점을 탐색합니다.
풀이 절차
- 크기 105 × 105의 메모이제이션 배열
memo를 선언합니다. - 재귀 함수
solve(s, idx, k, dp)를 정의합니다.idx가 문자열 길이와 같다면, k가 0일 때 0을 반환하고 그렇지 않으면 1000(사실상 불가능한 값)을 반환합니다.memo[idx][k]가 -1이 아니라면 이미 계산된 값을 그대로 반환합니다.- k ≤ 0이라면 무한대(INT_MAX)를 반환합니다.
- ans를 무한대로 초기화한 뒤, i를 idx부터 문자열 끝까지 이동시키면서
dp[idx][i] + solve(s, i+1, k-1, dp)의 최솟값을 갱신합니다.
- 메인 메서드에서는 다음을 수행합니다.
- n := 문자열의 길이로 설정하고, memo 배열을 -1로 초기화합니다.
- 크기 n × n의 2차원 배열
dp를 생성합니다. 여기서dp[i][j]는 구간 [i, j]를 회문으로 만들기 위해 필요한 최소 문자 변경 횟수를 의미합니다. - 구간 길이 l을 2부터 n까지 늘려가며, 구간의 양 끝 문자 s[i]와 s[j]를 비교합니다. 두 문자가 다르면 비용을 1 더하고, 내부 구간 dp[i+1][j-1] 값을 활용해 점화식을 완성합니다.
- 마지막으로
solve(s, 0, k, dp)를 호출해 결과를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int memo[105][105];
lli solve(string s, int idx, int k, vector < vector <int> > &dp){
if(idx == s.size()) {
return k == 0? 0 : 1000;
}
if(memo[idx][k] != -1) return memo[idx][k];
if(k <= 0)return INT_MAX;
lli ans = INT_MAX;
for(int i = idx; i < s.size(); i++){
ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
}
return memo[idx][k] = ans;
}
int palindromePartition(string s, int k) {
int n = s.size();
memset(memo, -1, sizeof(memo));
vector < vector <int> > dp(n, vector <int>(n));
for(int l =2; l <= n; l++){
for(int i = 0, j = l - 1; j <n; j++, i++){
if(l==2){
dp[i][j] = !(s[i] == s[j]);
}else{
dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
}
}
}
return solve(s, 0, k, dp);
}
};
main(){
Solution ob;
cout << (ob.palindromePartition("ababbc", 2));
}입력
"ababbc"
출력
1
복잡도 분석
구간별 회문 변환 비용을 계산하는 데 O(n²)의 시간이 걸리고, k개의 분할 지점을 탐색하는 과정에서 상태의 수는 O(n × k), 각 상태마다 최대 O(n)번의 반복이 발생하므로 전체 시간 복잡도는 O(n²k), 공간 복잡도는 O(n²)입니다. 메모이제이션 덕분에 동일한 하위 문제를 중복 계산하지 않아 효율성이 크게 향상됩니다.