백준 1557번 [제곱 ㄴㄴ](C++)-yes6686- 티스토리

백준 문제 풀이: 1557 [제곱 ㄴㄴ]

---

문제 링크: https://www.acmicpc.net/problem/1557

문제 설명:

자연수 중에서 어떤 소수의 제곱으로 나누어 떨어지지 않는 수들을 제곱 ㄴㄴ 수라고 합니다. n번째 제곱 ㄴㄴ 수를 찾는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[150001]; // 소수를 판별하기 위한 배열
long long parr[150001]; // 소수의 제곱 저장 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 에라토스테네스의 체를 사용하여 소수 판별
    for (int i = 2; i < 150001; i++) arr[i] = i;
    for (int i = 2; i * i < 150001; i++) {
        if (!arr[i]) continue;
        for (int j = i * i; j < 150001; j += i) {
            arr[j] = 0;
        }
    }

    // 소수의 제곱 저장
    int s = 0;
    for (int i = 1; i < 150001; i++) {
        if (arr[i]) parr[s++] = arr[i] * arr[i];
    }

    long long reCnt = 0;
    int pretotalReCnt = 0;
    int curN = n;

    while (1) {
        reCnt = 0;

        // 포함 배제 원리를 사용하여 제곱 ㄴㄴ 수 개수 계산
        for (int i1 = 0; parr[i1] <= curN; i1++) {
            reCnt += curN / parr[i1];
            for (int i2 = 0; parr[i1] * parr[i2] <= curN && i2 < i1; i2++) {
                reCnt -= curN / (parr[i1] * parr[i2]);
                for (int i3 = 0; parr[i1] * parr[i2] * parr[i3] <= curN && i3 < i2; i3++) {
                    reCnt += curN / (parr[i1] * parr[i2] * parr[i3]);
                    for (int i4 = 0; parr[i1] * parr[i2] * parr[i3] * parr[i4] <= curN && i4 < i3; i4++) {
                        reCnt -= curN / (parr[i1] * parr[i2] * parr[i3] * parr[i4]);
                        for (int i5 = 0; parr[i1] * parr[i2] * parr[i3] * parr[i4] * parr[i5] <= curN && i5 < i4; i5++) {
                            reCnt += curN / (parr[i1] * parr[i2] * parr[i3] * parr[i4] * parr[i5]);
                            for (int i6 = 0; parr[i1] * parr[i2] * parr[i3] * parr[i4] * parr[i5] * parr[i6] <= curN && i6 < i5; i6++) {
                                reCnt -= curN / (parr[i1] * parr[i2] * parr[i3] * parr[i4] * parr[i5] * parr[i6]);
                            }
                        }
                    }
                }
            }
        }

        // 현재까지 계산된 결과가 같으면 종료
        if (pretotalReCnt == reCnt) {
            cout << curN;
            break;
        }

        // n번째 제곱 ㄴㄴ 수로 이동
        curN += (reCnt - pretotalReCnt);
        pretotalReCnt = reCnt;
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 에라토스테네스의 체를 사용하여 소수를 구한 뒤, 포함 배제 원리를 사용해 제곱 ㄴㄴ 수를 계산합니다.
• 구현 세부사항:
  • 제곱 ㄴㄴ 수는 소수의 제곱으로 나누어 떨어지지 않는 수입니다.
  • 포함 배제 원리를 이용해 n번째 제곱 ㄴㄴ 수를 찾습니다.
• 시간 복잡도: O(k ⋅ log log k) + O(2^m) (k는 소수의 범위, m은 포함 배제 원리의 깊이)

---

결과

제곱 ㄴㄴ 수의 개념을 포함 배제 원리로 계산하여 정확히 구합니다. 효율적인 소수 판별 및 포함 배제를 통해 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!