백준 2331. 반복수열

www.acmicpc.net/problem/2331

2331번: 반복수열

 

다시 푼문제, 이전글: tose33.tistory.com/7

 

 

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

int edge[10000000];

int nextnum(int n, int p) {
    int sum = 0;
    while(n != 0) {
        int res = 0;
        res = n % 10;
        sum += pow(res,p);
        n /= 10;
    }
    return sum;
}

int main() {
    int A, P;
    cin >> A >> P;

    int cnt = 1, res = 0;

    while(true) {
        if(edge[A] != 0) {
            res = edge[A]-1;
            break;
        }
        edge[A] = cnt;
        A = nextnum(A,P);
        cnt++;
    }
    cout << res;
}

 

문제에서 주어진 법칙에 따라 다음에 올 숫자를 리턴해주는 함수 nextnum를 만들고

충분히 큰 int형 배열을 만들어서 결과값이 인덱스 값이 되도록하고, 값이 몇번째인지 되도록한다.

예를들어 수열이 다음과 같으면

 

57 74 65 61 37 58 ...

 

edge[57] = 1

edge[74] = 2

edge[65] = 3

...

 

이렇게 값을 넣어주고, edge[nextnum]값이 0이 아니면 이미 수열에 있는 수라는 뜻이다.

그럼 그 edge[nextnum]-1 이 답이다.