[백준/Python3] 14935번: FA

문제

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

함수 F(x)는 입력으로 주어진 수 x의 첫 자리와 수 x의 자리수를 곱한 결과를 반환하는 함수이다.

예를 들어 x = 932 일때 F(x)는 9×3으로 27을 반환한다.

입력받은 x에 대해서 함수 F를 수행하고, 나온 결과값에 다시 함수 F를 수행하는 것을 반복한다. 계속 반복해서 수행했을 때 어느 시점에서부터 동일한 수가 나오는 경우, 입력 x를 FA수 라고 한다.

입력 x가 주어졌을때 이 수가 FA 수인지 출력하라.

입력

정수 x 가 주어진다. (0 ≤ x ≤ 10^100)

출력

정수 x가 FA수 라면 FA를 출력하고, 아니라면 NFA를 출력한다.

풀이

이번에는 조금 독특한 방식으로 문제를 접근해보겠습니다.

함수F(x)의 반복적 적용이 항상 일정한 값으로 수렴함을 증명하는 방식으로 접근해보겠습니다.

자연수의 첫 자리는 항상 1~9로 범위가 고정되어 있습니다.

그렇다면 우리가 고려해야 할 요소 중 남은 것은 자리수에 대한 부분입니다.

양의 정수(자연수)의 자리수는 log10(x)의 정수 부분에 1을 더한 값입니다.

이것이 결국 수렴한다는 것을 입력의 조건과 수학적 귀납법을 통해 증명한다면,

정수 ( n )의 자릿수는 d(n)으로 정의합니다.

d(1) = 1 이고 n = k 일 때, d(n)입니다.

정수의 범위 0 ≤ n ≤ 10100 내에서 d(n)을 무한히 적용하면 결국 1로 수렴한다고 가정합니다.

k + 1 의 자릿수는 ( d(k + 1) )입니다.

k + 1 이 1자리 수(1~9)일 경우, d(k + 1) = 1 입니다.

k + 1 이 2자리 수(10~99)일 경우, d(k + 1) = 2 입니다.

k + 1 이 3자리 수(100~999)일 경우, d(k + 1) = 3 입니다.

.

.

.

k+1이 입력 조건의 최대수 10^100일 경우 d(10^100) = 101

일반적으로 ( k + 1 )이 ( m )자리 수일 때, ( d(k + 1) )는 ( m )이 됩니다.

k + 1 이 3자리 수(100~999)일 경우, d(k + 1) = 3 이라는 사실과 d(n)을 무한히 적용한다는 점을 통해 입력 조건의 최대수 조차 1로 수렴하게 된다는 것을 알 수 있습니다.

자연수의 첫 자리에 대한 사실과 자릿수 구하는 함수의 1로의 수렴을 합쳐보면

결국 F(x)를 무한히 반복했을 때 1~9 사이의 자연수로 무한히 반복된다는 걸 알 수 있습니다.

따라서 입력의 조건으로 주어진 0 ≤ x ≤ 10100의 정수 x에서는 항상 FA가 나오게 됩니다.

코드

print("FA")