[백준 2331번] 반복수열 (C++)

문제링크 : https://www.acmicpc.net/problem/2331

2331번: 반복수열

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int A, P, cnt;
int check[300000]; //최대값 계산 (9^5*5)

void func(int n)
{
    check[n]++;
    if(check[n]>=3) return; //반복되는 구간시 탈출

    int tmp = 0;
    while(n)
    {
        tmp += pow(n%10, P); //D[n] 구하기
        n/=10;
    }
    func(tmp); //다음값 넘기기
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> A >> P;
    func(A);

    for(int i=1; i<300000; i++) if(check[i]==1) cnt++; //한번 나온 것만 카운트

    cout << cnt;

    return 0;
}

 

현재 값이 몇 번 나온지 카운팅할 배열을 선언해준다.

해당 배열의 크기는 해당 문제에서 나올수 있는 최대 값인 9^5*5의 값을 참고해서 30만을 선언했다.

 

그리고 재귀를 A를 시작으로 계산을 진행한다.

다음 값을 저장할 임시변수 tmp를 선언해주고, 현재 값에 10을 나눈 나머지의 값을 P 제곱하여 tmp에 더해준다.

다음 자릿수 계산을 위해 현재 값에 10을 나눠주고 이를 모든 자릿수에 대해 계산할 때까지 반복해준다.

 

이제 반복되는 구간시 재귀를 종료시키도록 해줘야 한다.

처음에는 단순히 현재 값이 2번 나온다면 반복되기 시작했기 때문에 바로 종료를 시켜줬다.

하지만 이 경우에 '반복되는 구간'을 체크한 것이 아니기 때문에 이후 값이 반복되는 것은 알고 있지만 아직 현재 갯수 자체는 1개씩으로 카운팅되어있기 때문에 출력시에 포함되어버린다.

따라서 현재 값이 2번이 아니라 3번 나오는 경우를 체크해야 확실하게 반복되는 구간을 체크할 수 있다.