196-algorithm

Coddy의 수학 수수께끼 코스 레슨 — 20개 중 20번째.

38을 예로 들어, 숫자를 뒤집어서 더하면 38 + 83 = 121이 되며, 이는 대칭수(palindromic)입니다.

모든 숫자가 이렇게 빨리 대칭수를 만들어내는 것은 아닙니다. 예를 들어,

37 + 73 = 110
110 + 11 = 121

즉, 37은 대칭수에 도달하는 데 두 번의 반복이 필요했습니다.

249로 시작하는 또 다른 예시입니다:

249+942=1191
1191+1911=3102
3102+2013=5115.

11, 343과 같은 대칭수는 0번의 반복으로 대칭수가 된 것으로 간주합니다.

임의의 양의 정수를 택하여 숫자를 뒤집은 다음, 원래의 숫자에 더합니다. 이것이 뒤집어서 더하기 과정(reverse-and-add process)의 연산입니다. 이제 대칭수가 나올 때까지 얻어진 합계에 대해 이 절차를 반복합니다. 이 절차는 대부분의 정수에 대해 빠르게 대칭수를 생성합니다.

뒤집어서 더하기 과정을 통해 대칭수가 절대 형성되지 않는 숫자를 리크렐 수(Lychrel number)라고 합니다. 대칭수를 생성하는 것으로 알려지지 않은 처음 몇 개의 숫자들, 즉 "리크렐 수 후보"는 196, 295, 394입니다. [https://mathworld.wolfram.com/196-Algorithm.html]

챌린지

중급

아직 아무도 증명하지 못했지만, 10진법 체계에서 196과 같은 일부 숫자는 결코 회문(palindrome)을 생성하지 않습니다. 이 챌린지의 목적을 위해, 우리는 반증되기 전까지는 해당 숫자를 리크렐(Lychrel) 수라고 가정합니다. 10,000 미만의 모든 숫자는 (i) 50회 미만의 반복 내에 회문이 되거나, (ii) 현재 존재하는 모든 컴퓨팅 성능을 동원해도 아직까지 회문으로 변환하는 데 성공하지 못했습니다.

10,000보다 작은 양의 정수를 인자로 받아, 회문이 되기까지 걸리는 반복 횟수를 반환하는 함수 isLychrel을 작성하세요.

50회 이상 반복해도 회문이 되지 않는 경우에는 -1을 반환하세요.

직접 해보기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = isLychrel(n);
    printf("%d\n", r);
    return 0;
}