**팰린드롬 인코딩 **
문제
준규는 심심해서 팰린드롬 인코딩이라는 새로운 인코딩 방법을 만들었다.
팰린드롬 인코딩은 0과 1로만 이루어진 자료만 인코딩 할 수 있으며, 다음과 같은 과정을 거친다.
문자열 S에서 짝수 길이인 팰린드롬 연속 부분 문자열을 찾는다.
팰린드롬은 앞에서부터 읽을 때와 뒤에서부터 읽을때가 똑같은 문자열을 말한다.
만약, 팰린드롬이 없는 경우에는 3단계로 간다.
찾은 팰린드롬 문자열 중에서 뒤의 절반을 지운다. 예를 들어, 찾은 문자열이 0110이면, 10을 지운다. 만약, 팰린드롬이 더 존재하면 다시 1단계로 돌아가고, 없으면 남은 문자열을 출력한다. 문자열 S가 주어졌을 때, 팰린드롬 인코딩을 했을 때, 나올 수 있는 결과 중에서 가장 짧은 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 1보다 크고, 50보다 작다.
출력
첫째 줄에 팰린드롬 인코딩을 했을 때 가능한 최소길이를 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
예제 입력 1
0111001
예제 출력 1
2
예제 입력 2
0
예제 출력 2
1
예제 입력 3
01010111100110101110000001011000101000010111000111
예제 출력 3
6
풀이
스택으로 어떻게 해보려고 해도 감이 안온다. dp도 안되고
아이디어는 ..001…로 끝나면 ..01로 끝나고, ..100..으로 끝나면 ..10으로 간다.
001이나 100뒤에는 날려버릴 수가 있다는 것이다.
너무 애드 훅이긴한데 하다보면 이 원리를 찾을 수가 있다.
그렇기에 입력받은 문자열을 찾으면서 001이나 100패턴을 찾고 뒤를 날려버린다.
그러면 문제는 앞에 남은 것들이 있는데 101010처럼 0과 1이 반복되면 지울 수가 없다.
하지만 1110 처럼 반복되는 수는 2개를 펠린드롬으로 보고 1개만 남을 때 까지 지울 수 있다.
이걸 구현하면 문제는 풀린다.
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
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long a, b, c;
int t;
int n, m;
string s;
cin >> s;
if(s.size()<=2){
cout<<s.size();
return 0;
}
int ssize=s.size();
s+="xy"; //오류 안나게 길이 조정
int ans=0;
string s2="";
for(int i=0;i<ssize;i++){
if(s[i]!=s[i+1] && s[i+2]==s[i+1]){
s2+=s[i];
s2+=s[i+1];
break;
}
else{
s2+=s[i];
}
}
s2+="x";
string s3 = "";
for(int i=0;i<s2.size()-1;i++){
if(s2[i]!=s2[i+1]){
s3+=s2[i];
}
else{
continue;
}
}
cout << s3.size();
return 0;
}