본문 바로가기

Algorithm/Brute Force

(C++) - 백준(BOJ) 1254 : 팰린드롬 만들기

반응형

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

 

1254번: 팰린드롬 만들기

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는

www.acmicpc.net

전수조사 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

문자열 s, 최대 팰린드롬 길이를 저장할 maxPalinLen을 선언한 후 적절히 입력받습니다.

📔 풀이과정

문자열의 중간이 팰린드롬일 때 마자 maxPalinLen에 해당 길이를 저장합니다.이후 문자열의 길이 - maxPalinLen이 추가해야할 단어의 길이가 됩니다.

📔 정답출력

(s.size() - maxPalinLen) * 2 + maxPalinLen를 출력합니다.


📕 Code

#include <bits/stdc++.h>
using namespace std;
string s;
int maxPalinLen;

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

int main(){
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(isPalindrome(s.substr(i))){
            maxPalinLen = max(maxPalinLen, (int)s.size() - i);
        }
    }
    
    cout << (s.size() - maxPalinLen) * 2 + maxPalinLen;
}

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.