[백준 알고리즘] 1644번 - 소수의 연속합 (투포인터, 정수론)

1. 개요

오랜만에 풀어본 정수론 문제이다. 사실 풀이 방법은 투포인터에 더 가깝다... 소수를 구하는 방법인 에라토스테네스의 체가 기억이 잘 나지 않았지만 그래도 어찌저찌 기억해서 풀었다. 아마 최선의 방법이 아니었을 수 있다.

 

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

---

---

2. 본문

- 문제 나누기

---

1. 필요한 범위의 소수를 전부 구한다. (나는 그냥 입력값까지 구했다.)

2. 투 포인터 탐색 진행.

- 값이 크다면 left를 올린다.

- 값이 작다면 right를 올린다.

---

투 포인터 알고리즘을 생각해낸다면 코드는 쉽다.

 

- 정답 코드

 

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

using namespace std;

int prime_number_tmp[4000005] = {0};
vector<int> prime_number;
// int N;

void init_prime_number(int N) {
    
    for(int i = 2; i <= N; i++) {
        prime_number_tmp[i] = i;
    }

    for(int i = 2; i <= sqrt(N); i++) {

        if(prime_number_tmp[i] == 0) {
            continue;
        }

        for(int j =  i * 2; j <= N; j += i) {
            prime_number_tmp[j] = 0;
        }
    }

    //vector에 소수 추가
    for(int i = 2; i <= N; i++) {
        if(prime_number_tmp[i] == i) {
            prime_number.push_back(i);
        }
    }
}

int main(void) {

    int ans = 0;
    int N;

    cin >> N;

    //init prime number
    init_prime_number(N);

    int left = 0;
    int right = 1;

    int tmp = 2;

    while(left < prime_number.size() && right <= prime_number.size()) {
        if(tmp == N) {
            ans++;
            if(right < prime_number.size()){
                tmp += prime_number[right];
                right++;
            }else {
                break;
            }
            
        }

        if(tmp < N) {

            if(right < prime_number.size()) {
                tmp += prime_number[right];
                right++;
            }else {
                break;
            }

        }else if(tmp > N) {
            tmp -= prime_number[left];
            left++;
        }
    }

    cout << ans;

    return 0;

}

 

3. 결어

오랜만에 문제를 완벽하게 이해하고 첫 제출에 정답을 맞춘 코드를 작성해서 정리해보았다. 난이도가 올라갈수록 알고리즘 설계 과정이 어렵지 코드는 짧아지는 것 같다. 물론 구현과 시뮬레이션 문제들은 제외이다...