happy318
팽도리블로그
happy318
전체 방문자
오늘
어제
  • 전체글 (252)
    • 공부 (5)
      • Algorithm 정리 (0)
      • 논문리뷰 (1)
      • C++ (2)
      • Python (2)
      • Java (0)
      • Back-end (0)
      • Front-end (0)
      • Embedded (0)
    • 코딩테스트 (218)
      • Python 문제풀이 (100)
      • C++ 문제풀이 (108)
      • Python template (9)
      • C++ template (1)
    • 일상 (20)
      • 맛집 (13)
      • 쇼핑 (5)
      • 아무 일상 (2)
    • 게임 (9)
      • 메이플스토리 (9)

최근 글

인기 글

hELLO · Designed By 정상우.
happy318

팽도리블로그

코딩테스트/C++ 문제풀이

[백준] 소수의 연속합

2023. 3. 4. 16:03

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

 

1644번: 소수의 연속합

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

www.acmicpc.net

우선 문제부터 간단하게 요약하면,

 

N이 주어지면, 연속된 소수의 합으로 N을 구성할 수 있는 경우의 수를 구해야 하는 문제입니다.

 

<Solution>

우선 N까지의 숫자들중 소수를 에라토스테네스의 체로 구합니다. 

 

그리고 이 소수들을 이용하여 누적합 배열을 만들어 두고, 총 몇개의 조합이 가능한지 투포인터 알고리즘을 이용하여 탐색하면 됩니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <vector>
#include <cmath>

#define MAX 4000000

using namespace std;

int N;
int isPrime[MAX+10];

vector <int> prime_number;
vector <int> prefix_sum;

int main(){
    cin >> N;

    // sieve of Eratosthenes
    for(int i = 2; i<=sqrt(N)+1; i++){
        if(isPrime[i]) continue;
        for(int j = 2*i; j <= N; j+=i){
            isPrime[j] = 1;
        }
    }
    for(int i = 2; i<=N; i++){
        if(isPrime[i]) continue;
        prime_number.push_back(i);
    }

    // build prefix sum vector
    prefix_sum.push_back(0);
    for(int i : prime_number){
        prefix_sum.push_back(prefix_sum.back() + i);
    }

    // two pointer
    int sIndex =0, eIndex = 0;
    int curSum = 0;
    int ans = 0;

    while(eIndex <= prefix_sum.size()){
        curSum = prefix_sum[eIndex]-prefix_sum[sIndex];

        if(curSum < N) eIndex++;
        else if (curSum > N) sIndex++;
        else {
            ans++; 
            eIndex++;
        }
    }

    cout << ans << endl;
    return 0;

}
반응형

'코딩테스트 > C++ 문제풀이' 카테고리의 다른 글

[백준] 부분합  (0) 2023.03.05
[백준] 도시 분할 계획  (0) 2023.03.05
[백준] 계단 수  (0) 2023.03.02
[백준] 부분수열의 합 2  (0) 2023.03.01
[백준] 2진수 8진수  (0) 2023.03.01
    '코딩테스트/C++ 문제풀이' 카테고리의 다른 글
    • [백준] 부분합
    • [백준] 도시 분할 계획
    • [백준] 계단 수
    • [백준] 부분수열의 합 2
    happy318
    happy318

    티스토리툴바