https://www.acmicpc.net/problem/5502
딱 보고 아 이거 이차원 dp네 라고 생각했는데 그 이후로 한 이틀간 못 풀었습니다...
은둔고수 님이 저에게 완성된 팰린드롬에서 뺀다고 생각해 보라고 힌트를 주셨는데, 그거 듣고 조금 고민하다가 풀었습니다.
$dp(i, j)$는 $i$번째 문자와 $j$번째 문자가 같으면 $dp(i+1,j-1)$이고 다르면 $min(dp(i+1, j), dp(i, j-1)) + 1$이 됩니다.
cologne 님이 처음에 원래 문자열과 뒤집은 문자열의 LCS를 구하면 된다고 했었는데, 굉장히 그럴듯한 풀이라 속을 뻔 했습니다. 은둔고수 님이 틀렸다고 말해주시지 않았으면 짜러 갈 뻔 했습니다. 근데 사실 왜 틀렸는지 아직 몰라요.
아래는 코드입니다.
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
using namespace std;
int T, n, memo[5050][5050];
string s;
vector<int> vec;
int32_t main(void) {
FastIO;
T = 1;
//cin >> T;
while (T--) {
cin >> n >> s;
for (int k = 0; k < n; k++) {
for (int i = 0; i + k < n; i++) {
int j = i + k;
if (s[i] == s[j]) {
if (k == 0) continue;
memo[i][j] = memo[i + 1][j - 1];
continue;
}
memo[i][j] = min(memo[i + 1][j], memo[i][j - 1]) + 1;
}
}
cout << memo[0][n - 1] << endl;
}
return 0;
}
'알고리즘 문제해결 > BOJ' 카테고리의 다른 글
BOJ 5821 쌀 창고 (0) | 2022.08.08 |
---|---|
BOJ 2185 직사각형의 합집합 (0) | 2022.08.07 |
BOJ 8872 빌라봉 (0) | 2022.08.03 |
BOJ 5859 Liars and Truth Tellers (0) | 2022.08.02 |
BOJ 1635 1 또는 -1 (0) | 2022.08.01 |