백준 2331 반복수열 Kotlin (dfs)

문제 출처 : https://www.acmicpc.net/problem/2331

2331번: 반복수열

문제

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

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

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=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)가 주어진다.

출력

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

알고리즘 분류

• 수학
• 구현

풀이

dfs문제이다.

우선 값의 범위는 9^5*5로 최대 30만을 넘지 않는다.

예제를 보면,

57 2일 땐

[57, 74, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]

의 수열이 나오게 된다.

본인은 이들의 수를 카운트해줬다.

아래 코드의 로직대로 풀어보면,

cntArr[57] = 1

cntArr[74] = 2

cntArr[65] = 3

cntArr[61] = 4

cntArr[37] = 5

cntArr[58] = 6

cntArr[89] = 7

cntArr[145] = 8

cntArr[42] = 9

cntArr[20] = 10

cntArr[4] = 11

cntArr[16] = 12

cntArr[37] = 13

37이 반복되는 부분의 시작임을 알 수 있고, 37이전 까지는 5 - 1개의 수가 있다.

즉 cntArr[현재 방문한 수]가 0이 아니라면(두 번째 방문이라면) cntArr[현재 방문한 수]-1을 출력하면 된다.

 

코드

val br = System.`in`.bufferedReader()
//1<=A<=9999
//1<=P<=5
var answer=0
val cntArr = IntArray(300000)
fun dfs(cur : Int, p : Int , cnt : Int, a : Int){
    if(cntArr[cur]!=0) {
        answer = cntArr[cur]-1
        return
    }

    cntArr[cur]=cnt

    //next
    var num = cur
    var next=0
    while(num>0){
        var pNum=num%10
        for(i in 1 until p){
            pNum *= num%10
        }
        next +=pNum
        num/=10
    }
    dfs(next,p,cnt+1, a)
}

fun main() = with(System.out.bufferedWriter()){
    val (a,p) = br.readLine().split(' ').map{it.toInt()}
    dfs(a,p, 1,a)
    write("$answer")
    close()
}