1695번: 팰린드롬 만들기
앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열
www.acmicpc.net
입력으로 주어진 수열에 무작위로 수를 끼워넣어 팰린드롬으로 만드는데 최소 몇개의 수를 끼워 넣으면 되는지 구하는 문제입니다.
이 문제는 간단하게 주어진 수열과 뒤집은 수열의 lcs를 구한 후 N에서 뺀 값이 답입니다.
메모리 손해를 보지 않기위해 슬라이딩 윈도우 기법을 사용하였습니다.
|
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
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
#define max(a, b) {a > b ? a : b}
using namespace std;
int dp[2][5001], list[5001];
int N;
void func() {
int t = 0;
for (int i = N; i >= 1; i--) {
for (int j = 1; j <= N; j++) {
if (list[i] == list[j]) {
dp[t][j] = dp[1 - t][j - 1] + 1;
}
else dp[t][j] = max(dp[1 - t][j], dp[t][j - 1]);
}
t = 1 - t;
}
cout << N - dp[1 - t][N] << '\n';
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 2201 이친수 찾기 (2) | 2021.03.24 |
|---|---|
| boj 2228 구간 나누기 (0) | 2021.03.21 |
| boj 9177 단어 섞기 (0) | 2021.03.19 |
| boj 10942 팰린드롬? (0) | 2021.03.12 |
| boj 17404 RGB거리 2 (0) | 2021.02.28 |