백준 14941번 [호기심](C++)-yes6686- 티스토리

백준 문제 풀이: 14941 [호기심]

---

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

문제 설명:

주어진 범위 [a, b]에서 소수의 합과 소수의 특성에 따라 계산된 값을 출력하는 문제입니다. 소수의 특성은 번갈아 가며 첫 번째 소수는 3배를 더하고, 두 번째 소수는 빼는 방식으로 구성됩니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[100001];    // 소수 여부 체크 배열
int sum1[100001];   // 패턴 1 누적 합
int sum2[100001];   // 패턴 2 누적 합

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

    int n;
    cin >> n;

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

    int check = 1;
    // 패턴에 따른 누적합 계산
    for (int i = 1; i < 100001; i++) {
        if (arr[i]) { // 소수일 경우
            if (check) { // 패턴 1
                check = 0;
                sum1[i] = 3 * arr[i] + sum1[i - 1];
                sum2[i] = sum2[i - 1] - arr[i];
            } else { // 패턴 2
                check = 1;
                sum1[i] = sum1[i - 1] - arr[i];
                sum2[i] = 3 * arr[i] + sum2[i - 1];
            }
        } else { // 소수가 아닐 경우 이전 값 유지
            sum1[i] = sum1[i - 1];
            sum2[i] = sum2[i - 1];
        }
    }

    int a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;

        // 범위 내 첫 소수 찾기
        int firstP = 0;
        for (int j = a; j <= b; j++) {
            if (arr[j]) {
                firstP = j;
                break;
            }
        }

        // 출력 결과 계산
        if (firstP == 0) {
            cout << 0 << '\n'; // 범위 내 소수가 없으면 0 출력
        } else {
            if (sum1[firstP] - sum1[firstP - 1] > 0) {
                cout << sum1[b] - sum1[a - 1] << '\n';
            } else {
                cout << sum2[b] - sum2[a - 1] << '\n';
            }
        }
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 에라토스테네스의 체를 통해 소수를 판별하고, 소수에 대해 특정 패턴의 누적 합을 계산합니다.
• 구현 세부사항:
  • 패턴 1: 첫 번째 소수는 3배를 더하고, 다음 소수는 뺍니다.
  • 패턴 2: 첫 번째 소수는 빼고, 다음 소수는 3배를 더합니다.
  • 입력 범위에서 첫 소수를 기준으로 결과를 결정합니다.
• 시간 복잡도: O(n + q ⋅ √k)
  • n은 에라토스테네스의 체 계산
  • q는 쿼리 수, k는 범위 [a, b]

---

결과

범위 내 소수와 그 특성에 따른 값을 정확히 계산합니다. 누적 합과 소수 판별을 효율적으로 활용하여 문제를 해결했습니다.

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