[BOJ] 2331. 반복수열

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

연산 결과가 몇 번째로 나왔는지(index)를 배열에 저장하는데,

연산 결과가 이미 나온 적이 있다면(배열에 이미 index가 저장되어있을 경우)

초기에 나왔던 index를 출력해주면 된다.

#. Code

#include <cstdio>
using namespace std;
#define ll long long
 
int a, p, ck[250000];
 
int poww(int x, int y)
{
    int i, res = 1;
    for (i = 0; i < y; i++) 
        res *= x;
 
    return res;
}
 
void solve(int x, int idx)
{
    if (ck[x]) {
        printf("%d\n", ck[x] - 1);
        return;
    }
 
    ck[x] = idx;
    int tmp = 0, m;
 
    while (x != 0) {
        m = x % 10;
        tmp += poww(m, p);
        x /= 10;
    }
 
    solve(tmp, idx+1);
}
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
    scanf("%d %d", &a, &p);
 
    solve(a, 1);
 
    return 0;
}

line 18~21) 이미 나온적이 있는 정수라면 최초로 나왔던 index를 출력

line 23) 몇 번째로 나온 정수인지 배열에 저장

#. Other Code

#include <cstdio>
using namespace std;
 
int arr[101];
 
int poww(int x, int y)
{
    int i, res = 1;
    for (i = 0; i < y; i++)
        res *= x;
 
    return res;
}
 
int main(void)
{
    int a, p, i, j;
    // freopen("input.txt", "rt", stdin);
    scanf("%d %d", &a, &p);
 
    arr[1] = a;
    for (i = 2; i <= 100; i++) {
        int n = arr[i-1];
 
        while (n != 0) {
            arr[i] += poww(n % 10, p);
            n /= 10;
        }
 
        for (j = 1; j < i; j++) {
            if (arr[i] == arr[j]) {
                printf("%d\n", j - 1);
                return 0;
            }
        }
    }
 
    return 0;
}

* 시간 복잡도가 O(n^2)이 나와서 비효율적일 줄 알았는데, 오히려 메모리도 효율적이고 0ms 이내로 연산을 해버린다. 

  생각보다 반복수열이 길진 않나보다..ㅋㅋ

line 30~35) 연산 결과가 나왔던 적이 있었는지 확인하는 과정

 이 부분에서 시간 복잡도가 늘어날 줄 알았는데 생각보다 빨리 반복 수열이 나와서 괜찮았다.