백준(C) 1644번 [소수의 연속합]

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

소수의 연속합 1644번

 

 

접근방법

소수의 연속합 문제는 저번 문제와 같은 연속된 소수들의 합이 n이 되는 경우의 수를 세는 문제이다.

연속된 이라는 말이 있으니 투포인터를 사용하면 시간 효율성이 높아질것이고, 소수를 판별해야 하니 소수 판별법을 써서 소수를 걸러내야 될것이다. 그래서 나는 이렇게 구상했다.

 

1. 소수 목록 만들기

2. 투포인터로 경우의 수 찾기(오른쪽 포인터가 n을 넘으면 탈출)

3. 출력

 

일단 소수 목록은 사람들이 많이 쓰는 에라토스테네스의 체를 쓰기로 했다.

에라토스테네스의 체는 특정범위의 소수를 빨리 찾는 알고리즘으로 대량으로 바르게 찾는 방법이다.

방법은 다음과 같다.

1. 소수가 아닌 1을 제거한다.

2. 2부터 소수인 수의 배수를 제거한다.(지워진 수는 건너뛴다. 소수가 아니므로)

3. n까지 반복하고 남은 수는 소수이다.

 

이렇게 소수값 배열을 만든뒤 투포인터로 연속된 소수들의 합을 만들었다.

while 반복문 안에는 다음과 같은 조건문을 넣었다.

 

1. 연속된 값의 합이 n과 같으면 out(출력값)증가 아니면 n보다 크면 l 포인터값 증가

2. 연속된 값이 n보다 작은데 r포인터 값이 n과 같으면 break(n보다 큰 수는 나오지 못하므로) 아니면 r 포인터 값 증가

 

그리고 마지막 out값을 출력하여 완료하였다.

 

소수값 배열 + 투포인터 문제이다. 문제의 난이도가 올라갈수록 구현이 어렵게 나오던가, 여러가지의 알고리즘이 합쳐진 방법의 문제가 나오는것같다.

 

 

코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(void)
{
    int n, out = 0;
    scanf("%d", &n);
    bool num[4000001];
    int sosu[4000001];

    for (int a = 2; a <= n; a++)
        num[a] = true;

    for (int a = 2; a <= n; a++)
    {
        if (num[a] == 0)
            continue;

        for (int b = 2 * a; b <= n; b += a)
        {
            num[b] = 0;
        }

    }
    int c = 0;
    for(int a=2;a<=n;a++)
    {
        if(num[a])sosu[c++] = a;
    }

    int l = 0, r = 0, sum = 0;
    while (1)
    {
        if (sum >= n)
        {
            if(sum == n)out++;
            sum -= sosu[l++];
        }
        else
        {
            if(r == c)break;
            sum += sosu[r++];
        }
    }

    printf("%d\n",out);
    return 0;
}