https://www.acmicpc.net/problem/1053
다이나믹 프로그래밍 문제다. 즉, 점화식을 세워야 한다.
dp[i][j] = i 부터 j까지의 문자열을 팰린드롬으로 만들 수 있는 최소 연산 횟수.
dp[i][j] = min(dp[i+1][j] , dp[i][j-1], if(s[i] == s[j]) dp[i+1][j-1] else dp[i+1][j-2]+1)
문제는 4번 연산이다. 두 문자를 교환하는 연산을 최대 한 번 사용할 수 있는데... 언제 사용해야하는지 고민된다.
하지만 나중에 사용하게되면 별 효과가 없다. 이미 1,2,3 연산을 통해서 4번 연산이 만들 수 있는 효과를 만든 후이기 때문이다.
즉 처음부터 4번 연산을 적용해야한다.
import java.io.*;
public class boj1053 {
static StringBuffer s = new StringBuffer();
// i: 시작 j: 끝, 즉 dp[i][j] = i ~ j 범위까지 펠린 드롬 만드는 최솟값
static int[][] dp = new int[51][51];
static void swap(int src, int dst) {
char temp = s.charAt(src);
s.setCharAt(src, s.charAt(dst));
s.setCharAt(dst, temp);
}
public static void dps(int[][] dp, int ch, int ta) {
// 문자 위치 바꾸기
swap(ch, ta);
// dp 배열 초기화하기
for (int i = 0; i < s.length(); i++) {
dp[i][i] = 0;
if (i < s.length() - 1) {
if (s.charAt(i) == s.charAt(i + 1)) dp[i][i + 1] = 0;
else dp[i][i + 1] = 1;
}
}
for (int i = 2; i < s.length(); i++) {
for (int j = 0; j + i < s.length(); j++) {
dp[j][j + i] = Math.min(dp[j + 1][j + i] + 1, dp[j][j + i - 1] + 1);
if (s.charAt(j + i) == s.charAt(j)) dp[j][j + i] = Math.min(dp[j + 1][j + i - 1], dp[j][j + i]);
else dp[j][j + i] = Math.min(dp[j + 1][j + i - 1] + 1, dp[j][j + i]);
}
}
}
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int result = Integer.MAX_VALUE;
s.append(br.readLine().trim());
// 원래 문자열에서 팰린드롬 만드는 값 구하기
dps(dp, 0,0);
result = dp[0][s.length()-1];
// 이제 바꾼 문자열에서 팰린드롬 만드는 값 구한다.
for (int ch = 0; ch < s.length(); ch++) {
for (int ta = ch + 1; ta < s.length(); ta++) {
dps(dp, ch, ta);
result = Math.min(result, dp[0][s.length() - 1] + 1);
// 문자열 원상복구 시키기
swap(ch, ta);
}
}
bw.write(result + "\n");
bw.flush();
}
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 9370 미확인 도착지 (0) | 2020.09.08 |
---|---|
백준18809 Gaaaaaaarden (0) | 2020.09.06 |
백준 1958 LCS 3 (0) | 2020.09.06 |
백준 14444, 13275 가장 긴 팰린드롬 부분 문자열 (0) | 2020.09.04 |
백준 17071 숨바꼭질 5(java) (0) | 2020.09.04 |