🔥

문제

코딩 문제를 만들고 있는 윌리는 테스트케이스를 만들기 위해 무작위 수를 만들고 있다.
직접 랜덤한 수를 만드는데 지친 윌리는 당신에게 무작위 수를 만들어주는 프로그램을 만들어 달라는 부탁을 하였다.

랜덤한 수를 만드는 방법은 아래와 같다.

  1. 9999이하의 양의 정수 하나를 고른다.

  2. 그 정수의 가운데 두자리 (백의 자리와 십의 자리)를 고른다.

  3. 2번에서 고른 수를 제곱하면, 제곱한 수가 새로운 수가 된다.

  4. 2번과 3번을 반복하여 계속 수를 만들어간다.

예시는 아래와 같다.
7339 -> 33(가운데 두자리수)
-> 1089 (33의 제곱) -> 08(가운데 두자리수)
-> 64(8의 제곱) -> 06(가운데 두자리수)
-> 36(6의 제곱) -> 03(가운데 두자리수)
-> 9(3의 제곱) -> 0(가운데 두자리수)
-> 0(가운데 두자리수) -> 0…..

이 뒤로 0이 계속 반복된다.
7339의 경우에는 랜덤한 수를 계속 만들면 결국에 0이 되지만, 2245와 같은 수의 경우에는 0이 되지 않고, 같은 수가 반복된다.

2245 -> 24 ->
576 -> 57 ->
3249 -> 24 ->
576 -> 57 ->
3249 ….

이것처럼 576과 3249가 계속 반복되므로 더 이상 랜덤이라고 부를 수 없게 된다. 한번 나왔던 수가 다시 나오기까지 몇 번 반복해야 하는지 횟수를 구해보자.

7339의 경우에는 1089, 64, 36, 9, 0, 0처럼 6번 반복해야 한번 나왔던 수가 다시 나왔다.

입력

4자리 이하의 양의 정수 N이 주어진다.

출력

몇 번 위 동작을 반복 해야 한 번 나왔던 수가 다시 나오는지 그 횟수를 출력한다.

예제 1 입력

7339

예제 1 출력

6

예제 2 입력

2245

예제 2 출력

3

Source

n = int(input())
chk = [0 for _ in range(10000)]

def dfs(x, d):
	if(chk[x]):
		return d
	chk[x] = True
	middle = int(x / 10) % 100
	# 반환값이 있을 때 현재까지의 d값을 return
	return dfs(middle * middle, d + 1)

print(dfs(n, 0))

참고