[백준/C++]#2331 - 반복수열

풀이

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

pair<int,int> a[300000];
bool check[300000];
int cnt = 0;

void dfs(string N, int P) {
    int node = std::stoi(N);	// 문자열 -> 정수
    check[node] = true;
    
	int findNext = 0;		// 다음에 연결되는 노드 계산
    for (int i=0; i<N.size(); i++) {
    	findNext += pow(N[i]-'0', P);
    }
    a[node] = make_pair(findNext, cnt++);
    int next = a[node].first;
    if (check[next] == false) {
     	string nextS = std::to_string(next);	// 정수 -> 문자열
        dfs(nextS, P);
    }
    else {
     	cout << a[next].second;		// dfs가 끝날 때 값 출력
    }
}

int main() {
    string n;
    int p;
    cin >> n >> p;
    dfs(n, p);
    return 0;
}

개념

문자열을 숫자로 바꾸고, 숫자를 문자로 바꾸는데 string 라이브러리가 사용된다.

std::stoi (문자열 -> 숫자), std::to_string (숫자 -> 문자열)

 

제곱값을 계산하기 위해 cmath 라이브러리의 pow(a,b) 함수를 사용했다.

 

또한 pair 함수로 배열을 나타냈는데, 이 때 utility 라이브러리를 사용한다.

pair에는 그 값을 make_pair(a, b)를 통해 a와 b 값을 대입할 수 있다.

---

풀이

반복되는 수열 문제는 탐색 문제로 해결 할 수 있다.

각 숫자를 node로 생각하고, 다음 node를 앞선 노드로 계산하면 된다.

 

node : 57 -> 74 (5^2 + 7^2)

이런 식으로 이동한다.

 

방향그래프의 형태이고, node는 하나의 node로만 이동한다.

따라서 일차원 배열을 통해서 문제를 해결할 수 있다.

다만 해답을 계산하려면, 탐색한 노드의 순서에 해당하는 index값이 따로 필요하다.

이는 pair를 통해 구할 수 있다.

 

탐색이 진행되는 모습

 

배열에 저장된 실제 모습

dfs를 사용하는데, 탐색을 하다보면 탐색 실패지점이 존재한다.

탐색 실패지점의 순서 index 값이 구하고자하는 값이다.

이는 check[next] == true 일 때 a[next].second를 통해 계산한다.

 

다음 노드 계산에는 각 자릿수 숫자를 사용하기 때문에, 숫자값을 string으로 입력 받는다.

또한 자릿수 계산 이후에 다음 배열 index를 참조하기 위해 string 값을 숫자로 바꿔서 사용한다.

---

+a

※

배열의 크기는 가장 문제가 커지는 상황을 생각했다.

A=9999, P=5 일때 다음에 참조할 노드는 295,245이다.

따라서 배열의 크기를 300000으로 지정했다.

※

 

다른풀이(from 백준github)

#include <iostream>
using namespace std;
int check[1000000];
int pow(int x, int p) {
    int ans = 1;
    for (int i=0; i<p; i++) {
        ans = ans * x;
    }
    return ans;
}
int next(int a, int p) {
    int ans = 0;
    while (a > 0) {
        ans += pow(a%10, p);
        a /= 10;
    }
    return ans;
}
int length(int a, int p, int cnt) {
    if (check[a] != 0) {
        return check[a]-1;
    }
    check[a] = cnt;
    int b = next(a, p);
    return length(b, p, cnt+1);
}
int main() {
    int a, p;
    cin >> a >> p;
    cout << length(a, p, 1) << '\n';
    return 0;
}

각 자릿수에 접근하기 위해서는 무조건 string을 사용해야한다고 생각했는데, 이러한 방법이 있었다.

next 함수를 구성하는 방식이 더욱 간편하게 생각된다.

그외에는 유사한 방식이다.

문제 풀때도 생각했었지만, 역시 pair 없이도 해결할 수 있었다.