[백준] 1644번 : 소수의 연속합

문제

 

---

풀이

 

그냥 모든 배열을 탐색하면서 풀면 시간복잡도가 O(n^2)이 나와서 시간초과가 뜬다.

그러니까 투 포인터를 써야한다.

 

myunji.tistory.com/362

[백준] 2470번 : 두 용액

이 문제에서는 양방향에서 좁혀왔는데, 이번엔 한쪽에서 출발할 것이다.

 

일단 8이하의 모든 소수를 저장한 배열이 있다고 하자.

양 포인터 사이에 있는 모든 수를 합하면 2가 나온다.

우리의 목표 숫자인 8보다 작다. 그럼 오른쪽 포인터를 하나 증가해서 범위를 넓혀준다.

 

원래 한 칸만 옮겨야 하는데 2+3=5도 8보다 작으니 생략하고 바로 다음으로 옮겨왔다.

이제 양 포인터 사이의 모든 수를 합하면 10이 나온다. 이건 8보다 크다.

그럼 왼쪽 포인터를 옮겨서 범위를 줄여야겠다.

 

이제 범위 내의 숫자 합이 8이다. 조건에 충족하는 것이다.

이런 경우에는 왼쪽, 오른쪽 포인터를 모두 오른쪽으로 한칸씩 옮겨줘야 하는데

난 코드상 그냥 왼쪽 포인터만 옮겼다.

 

아무튼 두 포인터 중 하나라도 배열의 범위를 넘어가면 반복문을 종료한다.

---

소스코드

 

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

using namespace std;

vector<int> prime;

void eratos(int N) { //에라토스테네스의 체
    vector<bool> isPrime;
    isPrime.assign(N + 1, true);
    isPrime[0] = isPrime[1] = false;

    int line = sqrt(N) + 1;
    for (int i = 2; i <= line; i++) {
        if (isPrime[i]) {
            for (int j = i * 2; j <= N; j += i)
                isPrime[j] = false;
        }
    }
    for (int i = 2; i < N + 1; i++) { //구한 소수들 벡터에 넣기
        if (isPrime[i])
            prime.push_back(i);
    }
}

int cntPromise(int N) {
    int cnt = 0;
    int left = 0, right = 0; //왼쪽에서 시작

    int sum = prime[left];
    while ((left < prime.size()) && (right < prime.size())) { //범위 내에 있을 떄
        if (sum >= N) { //N 이상이면 left 증가
            if (sum == N) //N과 같으면 cnt 증가
                cnt++;
            sum -= prime[left];
            left++;
        } else { //N 미만이면 right 증가
            if (right < prime.size())
                sum += prime[right + 1];
            right++;
        }
    }
    return cnt;
}

int main() {
    int N;

    cin >> N;
    if (N == 1) { //1인 경우 처리
        cout << 0;
        return 0;
    }
    eratos(N); //소수 구하기
    cout << cntPromise(N);
}

소수 구하기에는 에라토스테네스의 체를 사용했다.

입력값이 1인 경우는 따로 처리했다.

 

vector<int> prime;

void eratos(int N) { //에라토스테네스의 체
    vector<bool> isPrime;
    isPrime.assign(N + 1, true);
    isPrime[0] = isPrime[1] = false;

    int line = sqrt(N) + 1;
    for (int i = 2; i <= line; i++) {
        if (isPrime[i]) {
            for (int j = i * 2; j <= N; j += i)
                isPrime[j] = false;
        }
    }
    for (int i = 2; i < N + 1; i++) { //구한 소수들 벡터에 넣기
        if (isPrime[i])
            prime.push_back(i);
    }
}

그냥 에라토스테네스의 체인데 마지막에 구한 소수들을 prime 벡터에 저장했다.

 

int cntPromise(int N) {
    int cnt = 0;
    int left = 0, right = 0; //왼쪽에서 시작

    int sum = prime[left];
    while ((left < prime.size()) && (right < prime.size())) { //범위 내에 있을 떄
        if (sum >= N) { //N 이상이면 left 증가
            if (sum == N) //N과 같으면 cnt 증가
                cnt++;
            sum -= prime[left];
            left++;
        } else { //N 미만이면 right 증가
            if (right < prime.size())
                sum += prime[right + 1];
            right++;
        }
    }
    return cnt;
}

포인터는 둘 다 왼쪽에서 시작하고

두 포인터 모두 배열의 범위 내에 있을 때까지만 반복문을 돈다.

 

        if (sum >= N) { //N 이상이면 left 증가
            if (sum == N) //N과 같으면 cnt 증가
                cnt++;
            sum -= prime[left];
            left++;
        }

목표 숫자인 N이상이라면 왼쪽 포인터를 옮겨야 한다.

sum에서 현재의 왼쪽 포인터가 가르키는 값을 빼고, 포인터를 옮겨준다.

sum이 목표 숫자인 N과 같다면 cnt도 늘려준다.

 

        else { //N 미만이면 right 증가
            if (right < prime.size())
                sum += prime[right + 1];
            right++;
        }

N보다 작다면 오른쪽 포인터를 옮겨준다.

혹시 포인터를 옮긴 결과 배열 밖을 가리키게 되고, 그로인해 런타임 에러가 발생하지 않도록 신경쓰자.