2331. 반복수열

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

2331번: 반복수열

 

일단 풀긴 했는데 그래프? 스럽게 풀진 않은 것 같다. 

 

문제에서 나온 수열 생성 방식에 따라 수열을 만들다 보면 반복되는 구간이 생기는데 이 반복되는 부분을 제외했을 때 남는 수들의 개수를 구하는 문제이다.

 

nextnum

그렇다면 일단 제공된 수열 생성 방식에 따라 수열을 만들어야 한다.

static int nextnum(int num, int p) {
        int sum = 0;
        int temp = num;

        while(temp != 0) {
            sum += Math.pow(temp % 10, p);
            temp /= 10;
        }

        return sum;
    }

수열 생성 방식은 

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

즉 각 자릿수를 P만큼 곱하고 모두 더하면 다음 수가 된다.

여기서 p = 2이고

57에서 (5^2 + 7^2 = 74) 이다.

 

nextnum함수에서는 현재 수 int num, 몇 번 곱하는지 p를 인자로 받는다.

계산된 다음 수열의 수를 리턴한다.

 

---

 

// 스택에 다음 숫자 넣고 그 숫자가 스택 처음에서부터 있는지 체크
        while(true) {
            int nn = nextnum(st.get(idx), p); // 계산한 다음 숫자
            st.push(nn); // 스택에 넣음

            boolean none = true;
            // 스택 처음에서 부터 있나 확인
            for(int i = 0; i < idx; i++) {
                if(nn == st.get(i)) {
                    re_idx = i;
                    none = false;
                    break;
                }
            }
            if(!none) break; // !none이면 중복된 숫자

            idx++;
        }

그래프로 어찌 풀것인가..고민하다가.. 그냥 스택에 수열을 순서대로 넣으면서 그때마다 스택의 처음부터 중복됐는지 찾아보는 방식으로 만들었다. 

뭔가 그래프로 더 좋게 풀 수 있을 것 같긴 한데..

 

코드

import java.util.*;
import java.lang.Math;

public class Main {

    static int nextnum(int num, int p) {
        int sum = 0;
        int temp = num;

        while(temp != 0) {
            sum += Math.pow(temp % 10, p);
            temp /= 10;
        }

        return sum;
    }

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);

        int a = s.nextInt();
        int p = s.nextInt();

        Stack<Integer> st = new Stack<Integer>();

        st.push(a);
        int re_idx = 0;
        int idx = 0;
        // 스택에 다음 숫자 넣고 그 숫자가 스택 처음에서부터 있는지 체크
        while(true) {
            int nn = nextnum(st.get(idx), p); // 계산한 다음 숫자
            st.push(nn); // 스택에 넣음

            boolean none = true;
            // 스택 처음에서 부터 있나 확인
            for(int i = 0; i < idx; i++) {
                if(nn == st.get(i)) {
                    re_idx = i;
                    none = false;
                    break;
                }
            }
            if(!none) break; // !none이면 중복된 숫자

            idx++;
        }

        System.out.println(re_idx);
    }
}

---

Solution

 

코드

import java.util.Scanner;

public class Main {
    // 순번을 기록할 배열 변수를 만들어 둔다.
    // 배열의 인덱스로 생산되는 수열값을 사용할 것이기 떄문에
    // 만들어질 수열값도 큰 값이어야 한다.
    // 메모리가 허용되는 범위에서 대략 넉넉히 잡아둔다.

    static int[] order = new int[10000000];

    static int next(int v, int p) {
        int res = 0;
        while(v > 0) {
            int n = v % 10;
            int t = p;
            int add = 1;
            while(t-- > 0) add *= n;
            res += add;
            v /= 10;
        }
        return res;
    }

    static int length(int a, int p, int cnt) {
        // 이미 나온 수열이 생상된 상황이다
        // 자신의 순번에서 '1'을 뺀 값을 반환한다.
        if(order[a] != 0) return order[a] - 1;

        order[a] = cnt; // 순번을 매긴다
        int n = next(a, p); // 다음 수열값을 구한다

        return length(n, p, cnt + 1); // 재귀로 탐색 & 순번을 매겨 나간다
    }

    public static void main(String args[]) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int p = s.nextInt();

        int res = length(n, p, 1); // 정답을 찾는다.
        System.out.print(res);
    }
}

내 풀이와 다른 점은 스택을 쓰지 않고 배열을 아예 크게 만들었고 그 배열의 idx 자체를 이용했다.

수열의 다음 수를 구하는 next함수는 유사.

 

그리고 length 함수 안에서 next함수로 다음 수 구하고 재귀로 탐색을 이어나간다. 

계속 다음 수열을 구하고 order 배열에 추가하다가 order[a]가 0이 아닌 상황 즉 중복된 수랑 맞닥트리면 

자신 순번에서 1을 뺀 값을 반환.