1254번 팰린드롬 만들기

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

github : https://github.com/junho0956/Algorithm/blob/master/1254/1254/%EC%86%8C%EC%8A%A4.cpp

 

 

팰린드롬이 만들기 위해서 뒤에서부터 최소 0개이상의 문자를 붙여야된다는 조건이였습니다.

길이는 최대 1000이기 때문에 충분히 브루트포스로 해결할 수 있었습니다.

앞자리에 붙이고자 하는 갯수만큼 뒤에 붙였다고 생각하면

이미 앞자리 부분과 뒷자리 부분은 팰린드롬을 이루기 때문에, 전체탐색을 할 필요없이 

팰린드롬이 되는 부분을 제외한 부분만 탐색해주시면 됩니다.

 

#include <iostream>
#include <string>
using namespace std;
 
string str;
 
bool palin(int idx) {
 
    int len = str.size() - 1;
    for (int i = idx; i <= len; i++, len--) {
        if (str[i] != str[len]) return false;
    }
    return true;
}
 
int main() {
    cin >> str;
 
    for (int i = 0; i < str.size(); i++) {
        if (palin(i)) {
            cout << str.size() + i;
            break;
        }
    }
 
    return 0;
}