[백준] 소수의 연속합 (1644) Java. 투 포인터 (Two Pointers)

문제 링크

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

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과 같은 표현도 적합하지 않다.

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

 

입력

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

 

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

접근법

모든 경우의 수를 구하는 문제이지만, "투 포인터 (Two Pointers)"를 이용하면 O(N) 시간 복잡도로 아주 간단히 풀 수 있는 문제이다.

투 포인터를 사용해서 연속된 숫자의 누적합을 구하는 아주 전형적인 문제이다. (소수 내용만 살짝 더한 느낌)

 

투 포인터는 뭔가 굉장히 있어보이는 이름을 가지고 있지만, 말 그대로 배열의 원소를 가리키는 두 개의 포인터 (C에서의 포인터 아님)를 사용한다고 해서 투 포인터이다. 하나의 1차원 배열을 탐색할 때 일반적으로 1개의 포인터를 사용해서 탐색하지만, 두 개의 포인터를 사용하면 1차원 배열에서의 연속된 누적합을 쉽게 구할 수 있다.

 

이 문제에서는 연속된 소수의 누적합을 구한 뒤, 그 합이 N과 같은 경우의 수를 구해야 하므로 N 이하의 소수가 들어 있는 1차원 배열로 투 포인터가 어떻게 사용되는지 알아보자.

 

 

N이 17일 때, N 이하의 소수의 합을 구해서 배열을 만들면 위 그림과 같을 것이다. 위에서 두 개의 포인터를 사용해서 배열에 접근한다고 했으므로, 그림에서는 Left와 Right 라는 포인터로 배열에 접근하는 것을 확인할 수 있다.

 

투 포인터를 사용해서 연속된 숫자의 누적합을 구한다고 했는데, Left가 가리키는 숫자부터 Right가 가리키는 숫자까지의 연속된 숫자의 누적합을 구할 것이다. 위에서는 Left == Right == 0 이므로, 누적합이 2임을 확인할 수 있다.

 

문제에서 원하는 것은 누적합이 17이 되는 경우의 수인데, Left == Right == 0 일 때의 누적합은 2. 17에 비해 한참 부족하다. 이 경우에는 두 개의 포인터 중 Right를 1 증가시키면서 누적합에 Right가 가리키는 숫자를 더해준다.

 

이렇게 하면 누적합을 구할 때 Left가 가리키는 숫자부터 Right가 가리키는 숫자를 전부 더해서 누적합을 새로 구할 필요 없이, 1개의 숫자만 더해주면 현재 상태의 누적합을 얻을 수 있음을 알 수 있다. 이것이 바로 투 포인터를 사용하는 이유이다. 포인터가 갱신될 때, 연속된 숫자의 범위가 바뀔 때마다 O(1)만에 누적합을 구할 수 있기 때문이다.

 

이 방법으로 누적합이 17 이상이 될 때 까지 Right를 1씩 증가시키며 누적합을 갱신해보자.

Right가 7을 가리킬 때 누적합이 N과 같아졌다! 따라서 2 + 3 + 5 + 7일 때 누적합 == N 인 경우가 존재함을 찾았으므로 경우의 수를 1 증가시켜준다.

 

그런데 우리는 누적합 == N 이 되는 모든 경우를 찾아야하므로 여기서 멈추면 안된다. 따라서 다른 연속된 숫자의 경우를 찾아야하므로 Right를 1 더 증가시켜준다.

Right가 11을 가리키게 되면서 누적합이 2 + 3 + 5 + 7 + 11로 28이 되었다. 여기서 처음으로 누적합이 N보다 커졌다. 누적합이 N보다 크므로, 숫자의 합을 줄여야 한다. 즉 연속된 숫자의 범위를 줄여야한다. 방법은 간단하다. Left를 1씩 증가시키면서 누적합을 갱신하면 된다. Right를 1씩 증가시킬 때는 숫자가 하나씩 추가되었으므로 누적합이 커졌지만, Left가 증가하면 숫자가 하나씩 빠지므로 누적합이 작아진다.

여기서도 마찬가지로 누적합이 N과 같아질 때 까지 Left를 늘려가면 된다. 과정 그림은 너무 길어지니까 생략하고, Left가 7을 가리킬 때 부터 보자.

아직도 누적합이 N보다 크다. 따라서 Left를 1 더 증가시킨다.

이번엔 누적합이 N보다 작아졌다! 이럴 땐 당황하지 말고 다시 Right를 늘려주면서 누적합이 N과 같아질 때를 찾으면 된다.

 

이렇게 누적합이 N보다 작을 때는 Right를 증가시키며 누적합을 크게 만들고, 누적합이 N보다 클 때는 Left를 증가시키며 누적합을 작게 만드는 식으로 연속된 숫자의 합이 N과 같아지는 경우를 전부 찾으면 된다.

 

위 예시에서는

이 경우까지 총 2가지의 경우가 있을 것이다.

 

주의할 점은 이 문제에서 처럼 투 포인터로 연속된 숫자의 누적합을 구할 수 있는 것은 반드시 숫자들이 정렬되어 있어야 한다는 것이다. 숫자들이 정렬되어 있지 않으면 Left와 Right를 위의 방식처럼 움직이는 것이 불가능하다.

 

정리하자면 이 문제에서는

1. N 이하의 소수의 배열 만들기 (에라토스테네스의 체 알고리즘 사용. 모르면 구글링 하면 바로 나온다)
2. 소수의 배열에서 투 포인터 사용해서 연속된 숫자의 누적합 구하기
3. 누적합이 N과 같으면 경우의 수 1 증가시키기

이렇게만 하면 정답을 구할 수 있다. 자세한 건 코드를 직접 보면 이해가 될 것이다.

 

 

시간 복잡도

O(N).

Left와 Right가 둘 다 배열 끝까지 이동하는 것이 worst case이고, 매 반복에서 Left 또는 Right가 1씩 증가하므로 최대 2N이 걸린다. 따라서 O(2N) -> O(N).

 

 

공간 복잡도

에라토스테네스의 체 알고리즘을 사용할 때 필요한 N + 1 크기의 boolean 배열

소수를 저장할 배열

N이 최대 4,000,000이고, 4,000,000 이하의 소수의 개수는 그리 많지 않으므로 메모리 사용량은 크지 않다.

 

 

풀면서 놓쳤던 점

딱히 없다.

 

 

이 문제에서 얻어갈 점

투 포인터 복습.

 

 

코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        //N < 2이면 N 이하의 소수가 존재하지 않으므로 0 출력하고 종료
        if (N < 2)
        {
            System.out.println(0);
            return;
        }

        //N 이하의 소수에 대한 arraylist
        ArrayList<Integer> primeNumbers = new ArrayList<>();
        getPrimeNumbersLessThanN(primeNumbers, N);

        //정답 구하고 출력
        System.out.println(countCases(primeNumbers, N));
    }

    //two pointers 를 이용해서 연속된 소수의 누적합을 오버헤드 없이 갱신
    //누적합이 N과 같으면 cnt++ 후 rightIdx++ & leftIdx++
    //N보다 작으면 rightIdx++, 크면 leftIdx++ 하며 누적합 갱신.
    //증감 연산자의 전위/후위에 주의하자.
    static int countCases(ArrayList<Integer> primeNumbers, int N)
    {
        int leftIdx, rightIdx;
        int cnt;
        int sum;

        leftIdx = 0;
        rightIdx = 0;
        cnt = 0;
        sum = primeNumbers.get(0);

        //사실상 leftIdx > rightIdx가 되는 경우는 while문 안에 있는 break 문 때문에
        //발생하지 않는다.
        while (leftIdx <= rightIdx)
        {
            if (sum == N)
            {
                cnt++;
                if (rightIdx + 1 == primeNumbers.size())
                    break;
                sum -= primeNumbers.get(leftIdx++);
                sum += primeNumbers.get(++rightIdx);
            }
            else if (sum < N)
            {
                if (rightIdx + 1 == primeNumbers.size())
                    break;
                sum += primeNumbers.get(++rightIdx);
            }
            else
                sum -= primeNumbers.get(leftIdx++);
        }

        return cnt;
    }

    //에라토스테네스의 체 알고리즘으로 N 이하의 모든 소수를 구하는 함수
    static void getPrimeNumbersLessThanN(ArrayList<Integer> primeNumbers, int N)
    {
        boolean[] primeCandidates = new boolean[N + 1];

        for (int prime = 2; prime <= N; prime++)
        {
            if (primeCandidates[prime])
                continue;

            primeNumbers.add(prime);

            //소수의 배수들을 모두 걸러낸다
            for (int j = 1; prime * j <= N; j++)
                primeCandidates[prime * j] = true;
        }
    }
}