BOJ 백준온라인져지 2331 반복수열 풀이

1. 9^5 의 5배는 295245

2. 즉 최댓값은 295245 라고 생각하고 풀었다.

3. 지금 생각해보니 더 높을수도 있겠다. (증명 또는 테스트 필요)

4. 결론적으로는 visited 라는 배열로 반복을 확인하고, list 에 넣으면서 값을 검사한다.

시간복잡도: O(295245) ??

공간복잡도: O(N)

문제

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이 때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1≤A≤9999), P(1≤P≤5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

예제 입력 1 

57 2

예제 출력 1 

4

힌트