백준 9421 _ 소수상근수

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

9421번: 소수상근수

---

✨ 내 소스 코드

#include<iostream>
#include <vector>
using namespace std;
int dp[1000001] = { 1, };
//0->한번 방문, -1->아님,1->맞음

int func(int n) {
    int sum = 0;

    while (n != 0) {
        sum += (n % 10) * (n % 10);
        n /= 10;
    }
    if (dp[sum]==-1) {
        return dp[sum];
    }
    if (sum == 1) {
        return 1;
    }
    if (dp[sum] == 0) {
        return -1;
    }
    dp[sum] = 0;
    dp[sum] = func(sum);
    return dp[sum];
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    vector<int> vec;
    cin >> N;
    fill_n(dp, 1000001, 1);
    for (int i = 0; i <= N; i++) {
        vec.push_back(i);
    }

    //에라토스테네스의 체
    for (int i = 2; i <= N; i++) {
        if (vec[i] == 0) {
            continue;
        }
        for (int j = 2; j*vec[i] <= N; j++) {
            vec[j*vec[i]] = 0;
        }
    }

    //상근수 탐색
    for (int i = 2; i <= N; i++) {
        if (vec[i] != 0) {
            if (func(vec[i])==1) {
                cout << vec[i] << '\n';
            }
        }
    }

    return 0;
}

 

🙏 문제 풀이

에라토스테네스의 체를 이용해 일단 소수를 걸러내고, 소수들 중에서 상근수인 것을 탐색

 

한 번 거쳐가게 되면 무조건 0으로 저장, 예시는 아래와 같다

• 2^2= 4 -> dp[4] = 0
• 4^2= 16 0 -> dp[16] = 0
• 1^2+ 6^2= 37 -> dp[37] = 0
• 3^2+ 7^2= 58 -> dp[58] = 0
• 5^2+ 8^2= 89 -> dp[89] = 0
• 8^2+ 9^2= 145 -> dp[145] = 0
• 1^2+ 4^2+ 5^2= 42 -> dp[42] = 0
• 4^2+ 2^2= 20 -> dp[20] = 0
• 2^2+ 0^2= 4 -> dp[4]는 이미 0이기 때문에 -1 반환

위의 dp[4] = dp[16] = dp[37] = dp[58] = dp[89] = dp[145] = dp[42] = dp[20] = -1이 됨

 

그 후 어떤 수의 계산을 하든 중간에 4, 16, 37, 58, 89, 145, 42, 20, 중에 하나가 나오면 위와 동일하게 계산이 진행되어 무한루프에 빠지기 때문에, 위의 숫자 중 하나가 나오면 무조건 상근수가 아님

 

if (dp[sum]==-1) { return dp[sum];} : 계산한 수가 이미 상근수가 아니라고 판명이 나있으면, 이후는 불필요한 계산이기 때문에 -1 값을 반환

 

상근수인 경우는 sum이 1일 때이다. 상근수가 맞으면 1을 반환하여 상근수가 아닐 경우와 동일하게 맞는 경우의 숫자들에 1의 값을 넣어준다

 

 

⭐ 문제 풀이 결과