[브루트 포스] BOJ 1254 팰린드롬 만들기

https://www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

 

문제 해결 알고리즘

 

문자열의 맨 끝 두 번째부터 시작해서 첫번째 문자를 붙여가면서 각각 팰린드롬인지 확인한다. 다음부터는 시작하는 문자열을 앞으로 한 칸 당겨서 진행해준다. 그렇게 첫번째까지 완료한 후 팰린드롬인 문장 중 가장 작은 길이를 출력한다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string str){
	
	bool flag = true;
	
	for(int i=0;i<str.size();i++){
		if(str[i] != str[str.size()-1-i]) flag = false;
	}
	
	return flag;
}

int main(){
	
	int result = 101;
	
	string str; cin >> str;
	
	if(str.size() == 1) {
		cout << 1;
		return 0;
	}
	
	for(int i=0;i<=str.size()-2;i++){
		int cnt = str.size()-2-i;
		string temp_str = str;
		
		do{
			if(isPalindrome(temp_str)){
				result = min(result, int(temp_str.size()));
			}
			
			temp_str += str[cnt--];
		
		}while(cnt >= -1);
	}
	
	cout << result;
}