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

2331번 : 반복수열

---

문제 )

다음과 같이 정의된 수열이 있다.

• D[1] = A
• D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게 된다.

 

 

입력 :

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

 

 

 

출력 :

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

 

 

 

 

 

풀이)

처음 푼 풀이이다. 이 풀이는 그냥 for문을 사용하여 계속해서 구하는 방식으로 풀었다.

 

#include <iostream>
#include <math.h>
#include <vector>
#include <string>
 
using namespace std;
 
int compare[9999999];
vector<string> vec;
 
int main()
{
    string a;
    int p;
    cin >> a >> p;
 
    vec.push_back(a);
    compare[stoi(a)] = 1;
 
    // 겹치는 수를 찾았을 경우 저장하기 위함
    string dup;
    while (1)
    {
        string temp = vec.back();
        // 2번째로 방문한다면 그 수를 저장
        if (compare[stoi(temp)] == 2)
        {
            dup = temp;
            break;
        }
 
        int make_number = 0;
        for (int i = 0; i < temp.length(); i++)
        {
            make_number += pow(stoi(temp.substr(i, 1)), p);
        }
 
        // 방문 횟수 기록
        compare[make_number]++;
        vec.push_back(to_string(make_number));
    }
 
    int answer = 0;
    for (auto& ele : vec)
    {
        if (ele == dup) break;
        answer++;
    }
 
    cout << answer;
 
    return 0;
}
 

 

 

DFS / BFS를 이용해서 풀 수 있다고해서 다시 풀어보았다.

 

해당 방법으로 메모리를 7배 가량 줄일 수 있었으나,

 

중간에 vector를 쓸데없이 써서 그런지 다른 제대로 된 답에 비해서는 3배정도 높게 잡혔다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <math.h>
 
using namespace std;
 
vector<int> visited(999999);
 
void bfs(string a, int p)
{
    string num = a;
 
    vector<string> vec;
    vec.push_back(num);
 
    queue<string> q;
    q.push(num);
    visited[stoi(num)]++;
 
    while (!q.empty())
    {
        string x = q.front();
        q.pop();
 
        if (visited[stoi(x)] == 2)
        {
            for (int i = 0; i < vec.size(); i++)
            {
                if (vec[i] == x)
                {
                    cout << i;
                    return;
                }
            }
        }
 
        int len = x.length();
        int temp = 0;
        for (int i = 0; i < len; i++)
        {
            temp += pow(stoi(x.substr(i, 1)), p);
        }
        q.push(to_string(temp));
        vec.push_back(to_string(temp));
        visited[temp]++;
    }
 
}
 
int main()
{
    string a;
    int p;
    cin >> a >> p;
 
    bfs(a, p);
 
 
    return 0;
}

---

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

2331번: 반복수열