Informatica Online Judge

  행복한 수 [0403 / 0193]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 169   Total Tried : 239


The Champion of this Problem (C++) : gs19022 - 0ms / 317byte
My Best Submission (C++) : N/A

[]

Background

행복한 수(happy number)는 각 자리수의 제곱의 합을 구해 나가는 과정을 연속적으로 적용하였을 때, 1까지 도달하는 수를 말한다. 좀 더 정확히 정의해 보자면, 주어진 양의 정수 n에 대하여 다음과 같은 수열을 정의할 수 있다:
n0, n1, n2, ...
여기에서, n0=n이고, ni+1은 ni의 모든 자리수의 제곱의 합이다. 만약에 이 수열에서 ni=1인 경우가 있으면 n은 행복한 수이다.
n이 행복한 수이면 위의 수열의 모든 ni는 행복한 수이다.
예를 들어, 7은 행복한 수인데 그 이유는 다음과 같은 수열이 만들어지기 때문이다
7, 49, 97, 130, 10, 1
7^2 = 49
4^2 + 9^2 = 97
9^2 + 7^2 = 130
1^2 + 3^2 + 0^2 = 10
1^2 + 0^2 = 1

하나의 양의 정수가 주어졌을 때, 주어진 정수보다 작거나 같은 정수 중에서 최대의 행복한 수를 구하는 프로그램을 작성하시오.

Input

하나의 정수 n이 입력된다. (1≤n≤1,000)

Output

입력된 양의 정수보다 작거나 같은 정수 중에서 가장 큰 행복한 수를 출력한다.

IO Example

예시1>
입력
8
출력
7

예시2>
입력
10
출력
10

예시3>
입력
355
출력
338

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]