algorithm/BOJ
BOJ 1695번 팰린드롬 만들기
_JunHo
2020. 2. 16. 20:05
BOJ : https://www.acmicpc.net/problem/1695
github : https://github.com/junho0956/Algorithm/blob/master/1695/1695/%EC%86%8C%EC%8A%A4.cpp
문자열을 앞 뒤 중간 어디든 넣을 수 있다면, LCS를 통하여 간단히 해결할 수 있다.
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
|
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 5001
int dp[MAX][MAX];
int arr[MAX];
int reverse_arr[MAX];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int N; cin >> N;
for (int i = 0; i < N; i++) cin >> arr[i], reverse_arr[N - i-1] = arr[i];
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
if (arr[i] == reverse_arr[k]) dp[i + 1][k + 1] = dp[i][k] + 1;
else dp[i + 1][k + 1] = max(dp[i + 1][k], dp[i][k + 1]);
}
}
cout << N - dp[N][N];
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|