백준 9213번 [꽤 좋은 수](C++)-yes6686- 티스토리

백준 문제 풀이: 9213 [꽤 좋은 수]

---

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

문제 설명:

자연수 (n)에 대해 약수의 합 (sigma(n))를 계산했을 때, (|sigma(n) - n|)이 주어진 badness 이하인 수를 "꽤 좋은 수"로 정의합니다. 주어진 구간 [s, e]에서 꽤 좋은 수의 개수를 구하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1000001]; // 약수의 합 저장 배열

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

    // 약수의 합 계산
    for (int i = 1; i < 1000000; i++) {
        for (int j = i * 2; j < 1000000; j += i) {
            arr[j] += i;
        }
    }

    int s, e, badness, cnt = 1;

    // 테스트 케이스 처리
    while (true) {
        cin >> s >> e >> badness;
        if (s == 0 && e == 0 && badness == 0) break;

        int ans = 0;

        // 꽤 좋은 수 개수 계산
        for (int i = s; i <= e; i++) {
            if (badness >= abs(arr[i] - i)) {
                ans++;
            }
        }

        cout << "Test " << cnt << ": " << ans << '\n';
        cnt++;
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 에라토스테네스의 체와 유사한 방법을 사용하여 약수의 합을 미리 계산하고, 각 테스트 케이스에서 조건을 확인합니다.
• 구현 세부사항:
  • 1부터 1,000,000까지의 각 수에 대해 약수의 합을 배열 arr에 저장합니다.
  • 주어진 구간 [s, e]의 각 수에 대해 (|sigma(n) - n|)을 계산하고, 조건을 만족하면 카운트합니다.
• 시간 복잡도: O(n log n) + O(t ⋅ k)
  • 약수의 합 계산: O(n log n)
  • 테스트 케이스 처리: O(t ⋅ k), t는 테스트 케이스 수, k는 각 구간의 길이

---

결과

구간 내에서 꽤 좋은 수의 개수를 정확히 계산합니다. 약수의 합을 미리 계산함으로써 각 테스트 케이스를 효율적으로 처리할 수 있습니다.

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