백준 1644번 소수의 연속합 :: 마이구미

이 글은 백준 알고리즘 문제 1644번 "소수의 연속합" 을 풀이한다.

접근은 에라토스테네스의 체를 통해 소수를 구하고, 투 포인터 또는 슬라이드 윈도우를 적용했다.

투 포인터 및 슬라이드 윈도우의 개념은 중요하지 않다.

본인 또한 구현하니 위와 같이 불리는 방식이였다.

에라토스테네스의 체는 다음 링크를 참고하자.

소수를 위한 에라토스테네스의 체 - http://mygumi.tistory.com/66

1644번 문제 - https://www.acmicpc.net/problem/1644

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

2 이상의 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

모든 소수를 구한 후, 연속된 소수의 합의 경우를 찾아야한다.

연속된 경우이기 때문에 부분합이 떠오를 수 있다.

2003번 "수들의 합 2" 문제의 경우에는 범위가 작기 때문에 시그마를 구현해서 풀 수 있다.

하지만 이 문제의 소수는 28만개정도 되기 때문에 시간초과가 된다.

소수를 구하는 부분에서는 크게 상관없이 어떠한 구현 방식으로 해도 문제가 되지 않는다.

연속된 소수의 합에 대한 경우의 수를 찾는 구현 방식이 중요하다.

먼저 소수 구하는 방식은 에라토스테네스의 체를 사용했다.

그리고 구해진 소수들을 하나의 배열로 저장했다.

public static void calPrime() {
    int sqrt = (int) Math.sqrt(MAX);
    for (int i = 2; i <= sqrt; i++) {
        if (array[i]) {
            continue;
        }

        for (int j = i + i; j <= MAX; j += i) {
            array[j] = true;
        }
    }
}

public static void setPrime() {
    for (int i = 2; i <= MAX; i++) {
        if (!array[i]) {
            prime[cnt++] = i;
        }
    }
}

부분합을 구하기 위한 시그마 배열을 만들면 다음과 같다.

P => 2 3 5 7 11 13 17
P[0] = 2
P[1] = 3
P[2] = 5
p[3] = 7
p[4] = 11

S => 2 5 10 17 28 41 58
S[0] = 2
S[1] = 5
S[2] = 10
S[3] = 17
S[4] = 28

S[0] = P[0]

S[1] = P[0] + P[1]

S[2] + P[0] + P[1] + P[2]

S[3] = P[0] + P[1] + P[2] + P[3]

S[4] = P[0] + P[1] + P[2] + P[3] + P[4]

위와 같이 나타낼 수 있다.

그렇기에, S[4] - S[1] 은 P[2] ~ P[4] 의 합이라는 것을 알 수 있다.

모든 경우의 범위의 부분합을 구할 수 있게 된다.

for(int i=1;i<=size;i++) {
    for(int j=i;j<=size;j++) {
        // sigma[j] - sigma[i-1]; 
        .....
    }
}

위에서 언급했듯이, 단순히 시그마 배열을 활용하여 부분합을 구하게 될 경우는 O(n^2) 으로 시간초과가 되기에 효율적으로 구현해야한다.

흐름은 같지만 시그마 배열을 구하는 것이 아닌, 마치 두 개의 포인터를 잡고 미는 듯이 구현한다.

두 개의 포인터는 부분합에 대한 시작 인덱스와 끝 인덱스를 말한다.

예를 들어 2 ~ 5 범위까지의 부분합이라고 한다면, 시작 인덱스는 2가 되고, 끝 인덱스는 5가 된다.

이 두개의 인덱스 포인터를 조작하면서 구현할 수 있다.

예를 들어 합이 41일 경우는 다음과 같다.

합이 될 수 있는 경우의 첫번째는 2 3 5 7 11 13 이다.

시작 인덱스는 0이 되고, 끝 인덱스는 5가 된다.

끝 인덱스를 증가시킨다는 것은 합이 증가된다는 의미이다.

시작 인덱스를 증가시킨다는 것은 합이 감소된다는 의미이다.

끝 인덱스를 증가시키면 41을 넘기 때문에 증가시키면 안된다.

그렇기에, 시작 인덱스를 증가시켜 합을 감소시켜가면서, 끝 인덱스를 증가시킬 수 있는 여부를 판단한다.

그 이후 다음 경우로 11 13 17 이 된다.

시작 인덱스는 4가 되었고, 끝 인덱스는 6이 된 모습을 볼 수 있다.

부분합을 이해했다면, 다른 설명없이 코드를 통해 이해할 수 있을 것이다.

흡사한 문제로써, 위와 같은 방법으로 해결 가능하다.

2003번 수들의 합2

1806번 부분합

static int MAX = 4000000;
static boolean[] array = new boolean[MAX + 1];
static int[] prime = new int[283146 + 1];
static int cnt;
 
private void solve() {
    int n = sc.nextInt();
    int ans = 0;
    int sum = 0;
 
    calPrime();
    setPrime();
 
    int s = 0, e = 0;
    while (e <= cnt) {
        if (sum < n) {
            sum += prime[e++];
            continue;
        }
 
        if (sum == n) {
            ++ans;
        }
 
        sum -= prime[s++];
    }
 
    System.out.println(ans);
}
 
public static void calPrime() {
    int sqrt = (int) Math.sqrt(MAX);
    for (int i = 2; i <= sqrt; i++) {
        if (array[i]) {
            continue;
        }
 
        for (int j = i + i; j <= MAX; j += i) {
            array[j] = true;
        }
    }
}
 
public static void setPrime() {
    for (int i = 2; i <= MAX; i++) {
        if (!array[i]) {
            prime[cnt++] = i;
        }
    }
}