(5) [C++, Java] 백준 No.2331 : 반복수열

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/398

# C++(비재귀 방식으로 구현)

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

int check[300000]; // 99999일 때 9^5 * 5 = 295245 이므로 그냥 300000으로 함.

// 다음 방문할 번호 구하는 함수
int get_next(int num, int p)
{
    int next = 0;
    while(num != 0){
        next += pow(num%10, p);
        num /= 10;
    }
    return next;
}

int main()
{
    // check 배열 초기화
    memset(check, 0, sizeof(check));

    int node, p;
    cin >> node >> p;

    // 첫번째 노드를 방문한 것으로 처리함
    int cnt = 1;
    check[node] = cnt;

    // 다음 방문할 번호를 계산함
    int next = get_next(node, p);

    // 사이클이 발견될 때 까지 탐색을 계속 진행함
    while(check[next] == 0){
        cnt += 1;
        check[next] = cnt;
        next = get_next(next, p);
    }

    // 사이클이 발견된 위치의 방문횟수에서 1을 빼준 값이 정답이 된다.
    cout << check[next] - 1;
}

# C++(재귀 방식으로 구현)

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

int check[300000]; // 99999일 때 9^5 * 5 = 295245 이므로 그냥 300000으로 함.

// 다음 방문할 번호 구하는 함수
int get_next(int num, int p)
{
    int next = 0;
    while(num != 0){
        next += pow(num%10, p);
        num /= 10;
    }
    return next;
}

// 탐색을 진행하며 방문순서를 기록하는 함수
int get_length(int a, int p, int cnt)
{
    if(check[a] != 0)
        return check[a] - 1;

    check[a] = cnt;
    int next = get_next(a, p);

    return get_length(next, p, cnt+1);
}

int main()
{
    // check 배열 초기화
    memset(check, 0, sizeof(check));

    int a, p;
    cin >> a >> p;
    cout << get_length(a, p, 1) << "\n";  //(첫 방문번호, p, 방문순서)
}

# Java

import java.util.*;

public class Main {
    public static int[] check = new int[1000000];
    public static int pow(int x, int p) {
        int ans = 1;
        for (int i=0; i<p; i++) {
            ans = ans * x;
        }
        return ans;
    }
    public static int next(int a, int p) {
        int ans = 0;
        while (a > 0) {
            ans += pow(a%10, p);
            a /= 10;
        }
        return ans;
    }
    public static int length(int a, int p, int cnt) {
        if (check[a] != 0) {
            return check[a]-1;
        }
        check[a] = cnt;
        int b = next(a, p);
        return length(b, p, cnt+1);
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int p = sc.nextInt();
        System.out.println(length(a, p, 1));
    }
}