[C/C++ 백준 1254번] 팰린드롬 만들기 (Silver 1)

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

1254번: 팰린드롬 만들기

 전에 보니까 팰린드롬인지 검사하는 문제도 있는거 같던데, 그걸 먼저 풀고 오면 좋았을 것이다.

간단해 보이면서도 은근 까다로운 문제다. 다이나믹 프로그래밍 카테고리에 있어서 dp로 풀 방법을 계속 고민해봤는데, 일단 dp를 쓰지 않고 푸는 방법으로 해결했다. 

 방법은, 앞에서부터 한 글자씩 뒤로 대칭시키며 매 번 팰린드롬인지 검사하는 것이다. 그러면 넘긴 다음숫자부터 끝까지가 팰린드롬인지 검사하여 맞으면 바로 break 시키고 넘긴숫자길이 + 원래숫자길이를 해주면 된다.

 

#include <cstdio>
#include <cstring>
int main(void){
	char S[1001];
	scanf("%s",S);
	int len=strlen(S);
	bool correct;
	for(int i=0; i<len; i++){
		correct=true;
		for(int j=i; j<len; j++){//펠린드롬 검사 
			if(S[j]!=S[len-1-(j-i)]){
				correct = false;
				break;
			}		 
		}
		if(correct){
			printf("%d",len + i);
			break;
		}
	}
}