알고리즘 문제
[C/C++ 백준 1334번] 다음 팰린드롬 수 (Silver 3)
새파란 공대생
2020. 7. 18. 08:56
https://www.acmicpc.net/problem/1334
1334번: 다음 팰린드롬 수
팰린드롬 수는 앞으로 읽어도, 뒤로 읽어도 같은 숫자이다. 101, 4, 6666와 같은 숫자는 팰린드롬 수이고, 10, 564, 15452와 같은 숫자는 아니다. 어떤 수 N이 주어질 때, N보다 큰 팰린드롬 수 중에서 가
www.acmicpc.net
실버 3밖에 안되는데, 정말 어려운 문제였던 것 같다.
기본적인 알고리즘은, 팰린드롬수간의 크기를 비교할때는 중간까지의 숫자의 크기를 비교하면 되는 것을 이용하는 것이다. 그래서 12321, 12421간의 크기를 비교할 때는 123, 124까지만 비교하면 된다. 크기를 키울때도 마찬가지로 저 세자리중 일의 자리수만 증가시키면 된다.
예제로 12345가 들어왔다고 가정하자. 우선 앞의 123을 대칭시켜 12321을 만들고, 12345와 크기를 비교하자. 이때 크기가 더 크면 바로 그걸 사용하고, 크기가 더 작다면 가운데 3을 증가시켜 12421을 만들면 된다. 이때 증가시키는 연산은 한 번만 일어난다.
다만, 9가 있을 경우는 자릿수를 계산하는 것처럼 해당 자리를 0으로 바꿔주고 윗자리를 1증가시켜주자.
9로만 이루어져 있을 경우는 자릿수가 바뀌므로 이런 경우는 따로 처리해준다.
코드는 다음과 같다.
#include <cstdio>
bool AisBiggerthanB(int *a, int *b, int n){
for(int i=0; i<=n; i++){
if(b[i]>a[i])
return false;
else if(a[i]>b[i])
return true;
}
return false;
}
int main(void){
int number[51], i=0, newnum[51], mid;
bool Allnine = true;
while(~scanf("%1d", &number[i])){
i++;
}
i--;
mid = i/2;
for(int k=0; k<=i; k++){
if(number[k] != 9)
Allnine = false;
}
if(Allnine){
printf("1");
for(int j=0; j<i; j++)
printf("0");
printf("1");
}
else{
for(int j=0; j<=i/2; j++){
newnum[j] = newnum[i-j] = number[j];
}
while(!AisBiggerthanB(newnum, number, i)){
newnum[mid]++;
if(mid != i - mid)
newnum[i-mid]++;
while(newnum[mid] == 10 && newnum[i-mid]==10){
newnum[mid] = newnum[i-mid] = 0;
mid--;
newnum[mid]++;
newnum[i-mid]++;
}
}
for(int k=0; k<=i; k++)
printf("%d",newnum[k]);
}
}