[백준] 2331. 반복수열 풀이

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

 

 

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

이고, 수열 D에서 반복적인 부분을 삭제하였을 때의 수열에 남게되는 수를 구하는 문제.

 

나는 이를 DFS를 통해 풀었다. (사실 단순히 한 방향으로 이루어지는 구조라서 재귀적인 방법으로 풀었다에 더 가깝다고 생각한다.)

 

우선 236197개의 요소를 가진 배열을 생성한다.

그 이유는 수열에서 나올 수 있는 최대 숫자가 9^2+9^2+9^2+9^2 = (9^2)*4 = 236197 이기 때문이다.

그 후 DFS함수를 이용해서 a의 각 자릿수의 p제곱한 값의 합을 저장한다.

 

이렇게 구한 합이 다음 수열의 값이 된다.

나중에 반복된 수열이 나오는지 확인해야 하므로 이를 저장해둔다. 

(나는 check배열을 만들어서 다음 수열을 계산하며 나온 값에 해당하는 인덱스에 1 혹은 True값을 저장했다.)

 

다음 수열들을 계산해나가다가 이미 나온 수열값이 있다면 탐색을 종료한다.

 

최종적으로 현재까지 나온 수열의 개수(= check에 저장된 1 혹은 True의 개수)를 출력하여 문제를 해결한다.

 

 

---

C

#include <stdio.h>
#define MaxSize 10000

int record[MaxSize];
int check[236197];

void append(int v){
    for(int i = 0; i < MaxSize; i++){
        if(record[i] == 0) {
            record[i] = v;
            break;
        }
    }
}

int DFS(int v, int p){
    check[v] = 1;
    append(v);
    int sum = 0;
    while(v > 0){
        int mtp = 1;
        for(int i = 0; i < p; i++) mtp *= v % 10;
        sum += mtp;
        v /= 10;
    }
    if(check[sum] == 1) return sum;
    else return DFS(sum, p);
}
int main() {
    int a, p; scanf("%d %d", &a, &p);
    int v = DFS(a, p);
    int cnt = 0;
    for(int i = 0; i < MaxSize; i++){
        if(record[i] == v) {
            printf("%d", cnt);
            break;
        }
        cnt += 1;
    }
}

---

Python

import sys
sys.setrecursionlimit(10 ** 6)

def DFS(v, p):
    check[v] = True
    record.append(v)
    sum = 0
    while v > 0:
        sum += (v % 10) ** p
        v //= 10
    if check[sum] == True:
        return sum
    else:
        return DFS(sum, p)
    
record = []
a, p = map(int, input().split())
check = [False for _ in range(236197)] # (9^5)*4
v = DFS(a, p)
cnt = 0
for i in record:
    if i == v:
        print(cnt)
        break
    cnt += 1