C언어 216제] 뒤집어서 더하기(Reverse and Add)

출처 : 반크_백제역사 유적지구와 이스탐블역사 유적지구

 

문제]

일단 어떤 수를  방아서 그 수를 뒤집은 다음 뒤집어진 수를 원래의 수에 더하는 과정을 뒤집어서 더하기라고 부르자, 그 합이 회문(palindrome, 앞뒤 어느 쪽에서 읽어도 같은 말이 되는 어구. 예: eye, madam, 소주만병만주소)이 아니면 회문이 될 때가지 이 과정을 반복한다.

예를 들어 처음에 195에서 시작해서 다음과 같이 네 번 뒤집어서 더하기를 반복하면 9,339라는 회문이 만들어진다.

195 + 591 = 786 + 687 = 1473 + 3741 = 5214 + 4125 = 9339

대부분의 정수는 이 방법을 몇 단계만 반복하면 회문이 된다. 하지만 예외도 있다. 회문을 찾을 수 없는 것으로 밝혀진 첫번째 수는 196이다. 하지만 회문이 없다는 것이 증명된 적은 없다.
어떤 수가 주어졌을 때 회문이 있으면 출력하고, 그 회문을 찾기까지 뒤집어서 더하기를 반복한 횟수를 출력하는 프로그램을 만들어야 한다.
테스트 데이터로 쓰이는 수는 모두 뒤집어서 더하기를 1,000번 미만 반복해서 회문을 찾을 수 있는 수고, 그렇게 만들어진 회문은 4,294,967,295보다 크지 않다고 가정해도 된다.

입력
첫번째 줄에는 테스트 케이스를 나타내는 정수 N(0<N<=100)이 들어있고, 그 아래로 N개의 줄에 걸쳐서 회문을 구해야 하는 정수가 한 줄에 하나씩 들어있다.

출력
N개의 각 정수에 대해 회문을 발견하는 데 필요한 최소한의 반복 횟수를 출력하고, 스페이스를 한 칸 출력한 다음, 그 회문을 출력한다.

입력 예
3
195
265
750

출력 예
4 9339
5 45254
3 6666



출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어): 문제34 뒤집어서 더하기(Reverse and Add) p153

 

참고풀이]

#include <stdio.h>

unsigned int Reverse(unsigned int x)
{
   unsigned int y=0;
   while(x>0)
   {
      y=(y*10)+(x%10);
      x/=10;
   }
   return y;
}

int main()
{
   int Num, iter;
   unsigned int n, r;

   scanf("%d", &Num);
   while(Num-- > 0)
   {
      scanf("%lu",&n);
      iter=0;
      while(n != (r=Reverse(n)))
      {
         n+=r;
         iter++;
      }
      printf("%d %lu\n", iter, n);
   }
   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 여름