백준 2213 - 반복수열

문제

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

2331번: 반복수열

 

 

풀이

수열 D의 숫자들이 반복되는 시작점을 N 이라고 했을 때 반복되는 부분을 제외한 나머지 부분의 개수는 N - 1 개가 된다. 그리고 숫자의 반복이 어디서부터 시작되는지 쉽게 알 수 있도록 그래프를 이용해 수열의 수들을 방문한 점과 방문하지 않은 점으로 구분한다. 결국 그래프에서 사이클을 제외한 길이를 구하는 문제가 된다.

 

1. A에 해당하는 노드를 방문한다. 방문 순서를 증가한다. 

2. A = next(A)를 방문하지 않았다면 방문한다. 방문 순서를 증가한다.

3. 2를 만족한다면 계속 반복한다.

4. 3이 끝났을때 A의 방문 순서 부터 사이클이 형성된다.

 

 

코드

#include <iostream>
#include <cmath>
 
using namespace std;
 
int P;
int A;
pair<int, bool> visit[236197];
int len = 1;
 
int nextPos(int idx)
{
    int next = 0;
    while (idx)
    {
        next += pow(idx % 10, P);
        idx /= 10;
    }
    return next;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> A >> P;
    visit[A] = make_pair(len, true);
 
    A = nextPos(A);
    while (!visit[A].second)
    {
        len++;
        visit[A] = make_pair(len, true);
        A = nextPos(A);
    }
 
    cout << visit[A].first - 1;
 
    return 0;
}