[BOJ] 행복한 소수(10434)

[백준(BOJ)] 행복한 소수(10434) C++

문제 : BOJ_10434번 행복한 소수

에라토스테네스의 체

문제 제목과는 달리 사람 참 불행하게 만드는 소수입니다...
이 문제에서는 어떤 수를 주었을 때, 두 가지 조건을 만족하는가를 탐색하는 문제입니다.

• 어떤 수가 행복한 수 인가? - 행복한 수는 주어진 수의 각 자릿수의 제곱을 곱해서 더 해주고 나온 수를 또 각 자릿수의 제곱을 곱해주는 방법을 반복해서 1이 될 수 있는 수를 의미합니다.
• 어떤 수가 소수인가? - 여기서 소수 판별을 수마다 해줘야 하는데, 테스트 케이스의 최대수는 1000, 각 테스트 케이스의 최대 번호는 10000이기 때문에 에라토스테네스의 체를 이용하지 않는다면 시간 초과가 되고 맙니다
• (에라토스테네스에 대한 자세한 설명은 이 블로그의 에라토스테네스의 체에서 다뤘습니다.)

위 두 조건을 만족한다면 그 테스트 케이스의 번호는 행복한 소수를 만족해서 YES가 출력되고 아니면 NO가 출력됩니다.

문제의 조건

(2) 번 조건은 에라토스테네스의 체를 이용해 소수인지 아닌지 판별해야 되고,
(1) 번 조건 같은 경우엔, 주어진 수를 자릿수의 제곱의 합들로 계속 바꿔보면서
색을 해야 됩니다. 이때, 1이 되기 전에 각 자릿수의 제곱들의 합이 원래 수로
반복되어서 나타난다면 1이 되지 않고 계속 반복한다는 의미이므로,
(1)의 조건을 만족 못 하는 것이고 그전에 1이 된다면 (1)의 조건을 만족하는 것입니다.

 

1. (1)의 조건을 만족 못 하고 반복되는 경우를 확인하는 것은 배열을 통해 확인 (dis_arr[]);
2. sqrt()를 써서 최대한 적은 횟수로 소수 판별 (cmath)
3. 각 테스트 케이스 앞에 테스트 케이스의 번호가 있는데 그 번호와 상관없이 입력한 수 순서대로 그대로 출력해야 됨!!! (테스트 케이스 앞 번호를 순서로 순서대로 한꺼번에 출력하면 오답 처리)

C++ 소스

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int era[10010], dis_arr[10010], roof; // dis_arr == 원래의 수로 반복되는지 확인해보기 위해 만든 배열
int happy(int x);
int main(void) {
    era[0] = 1;
    era[1] = 1;
    for (int i = 2; i < sqrt(10000); i++) { // 최대한 시간을 줄이기 위한 sqrt()
        if (era[i] == 1) continue;
        int cnt = 2;
        while (cnt*i <= 10000) {
            era[i*cnt] = 1;
            cnt++;
        }
    }
    cin >> roof;
    for (int i = 1; i <= roof; i++) {
        int a, b;
        cin >> a >> b;
        if (happy(b) == 1) {
            if (era[b] == 0) {
                cout << a << ' ' << b << ' ' << "YES" << '\n';
            }
            else cout << a << ' ' << b << ' ' << "NO" << '\n';
        }
        else cout << a << ' ' << b << ' ' << "NO" << '\n';
        memset(dis_arr, 0, sizeof(dis_arr));
    }
    return 0;
}
int happy(int x) { // 1을 return 하면 행복한 수 , 0을 return 하면 행복한 수가 아니다.
    while (1) {
        if (x == 1) return 1;
        if (x == 10000) return 1;
        else if (x >= 1000 && x < 10000) {
            x = (x / 1000)*(x / 1000) + ((x / 100) % 10)*((x / 100) % 10) + ((x / 10) % 10)*((x / 10) % 10) + (x % 10)*(x % 10);
            if (dis_arr[x] == 1) return 0;
            else dis_arr[x] = 1;
            continue;
        }
        if (x >= 100 && x < 1000) {
            x = (x / 100)*(x / 100) + ((x / 10) % 10)*((x / 10) % 10) + (x % 10)*(x % 10);
            if (dis_arr[x] == 1) return 0;
            else dis_arr[x] = 1;
            continue;
        }
        else if (x >= 10 && x < 100) {
            x = (x / 10)*(x / 10) + (x % 10)*(x % 10);
            if (dis_arr[x] == 1) return 0;
            else dis_arr[x] = 1;
            continue;
        }
        else if (x > 1 && x < 10) {
            x = x * x;
            if (dis_arr[x] == 1) return 0;
            else dis_arr[x] = 1;
            continue;
        }
    }
}