[백준] BOJ_20040 사이클 게임

이종찬·2026년 1월 5일
baekjoon
post-thumbnail

문제 정보

  • 문제 요약: 자연수 이 주어졌을 때, 이 정수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다. (한 개의 소수 자체도 포함됩니다.)
  • 핵심 제약:
  • (4백만)
  • 시간 제한: 2초
  • 메모리 제한: 128MB

접근 방식

이 문제는 두 단계로 나누어 생각해야 합니다. 첫째는 데이터 전처리(Preprocessing) 단계이고, 둘째는 탐색(Search) 단계입니다.

1. 문제의 본질: 연속성과 소수

우리가 다뤄야 할 수는 '소수(Prime Number)'입니다. 소수는 규칙적이지 않게 분포하므로 수식으로 바로 번째 소수를 계산하기 어렵습니다. 따라서 이하의 모든 소수를 미리 구해서 리스트로 만들어 두는 과정이 선행되어야 합니다.

또한, '연속된' 합을 구해야 한다는 점에 주목해야 합니다. 이는 임의의 소수 조합을 찾는 배낭 문제(Knapsack)가 아니라, 구간 합(Range Sum) 문제입니다. 소수는 모두 양수이므로, 구간의 길이가 길어지면 합은 커지고, 짧아지면 합은 작아집니다. 이 단조 증가(Monotonically Increasing) 성질 덕분에 투 포인터 알고리즘을 적용할 수 있습니다.

2. 알고리즘 설계

Step 1: 에라토스테네스의 체 (Sieve of Eratosthenes)
이 최대 4,000,000입니다. 매번 소수 판별 함수를 호출하면 시간 초과가 발생할 위험이 높습니다. O(Nlog⁡log⁡N)O(N \log \log N)의 시간 복잡도를 가지는 에라토스테네스의 체를 사용하여 한 번에 소수 리스트를 확보합니다.

Step 2: 투 포인터 (Two Pointers)
소수들이 담긴 리스트 primes가 있다고 가정해 봅시다.

  • left, right 두 개의 포인터를 0에서 시작합니다.
  • 현재 구간의 합(sum)이 보다 작다면 right를 이동시켜 합을 키웁니다.
  • 현재 구간의 합(sum)이 보다 크거나 같다면 left를 이동시켜 합을 줄입니다.
  • sum == N인 경우 카운트를 증가시킵니다.

3. 수식 및 점화식

소수 판별 로직에서 내부 반복문의 시작점에 유의해야 합니다. 가 소수일 때, 의 배수들을 지워나가는데, 부터 지우는 것보다 부터 지우는 것이 더 효율적입니다.

투 포인터의 상태 전이 조건은 다음과 같습니다. ( = 현재 부분 합)

(단, 일 때 count를 증가시킵니다.)

코드 구현

1. 실패한 코드 (Logic Error & Messy Implementation)

초기 접근에서는 소수를 구하는 로직에 치명적인 오류가 있었고, 투 포인터 구현도 불필요하게 복잡했습니다.

// 실패
class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static final int MAX_VALUE = 4_000_000;
    static int N;
    // visit 배열 사용 의도가 불분명하고, 로직에 제대로 반영되지 않음
    static boolean[] visit; 
    static List<Integer> primeNumbers;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        primeNumbers = getPrimeNumbers();

        // [문제점 1] 투 포인터 로직의 복잡성
        // while문 안에 중첩된 while문들이 있어 가독성이 떨어지고
        // 엣지 케이스(right가 끝에 도달했을 때 등) 처리가 미흡함
        int left = 0;
        int right = 0;
        int len = primeNumbers.size();
        int sum = 0;
        while (left <= right) {
            boolean calculate = false;
            while (sum < N && right < len) {
                sum += primeNumbers.get(right++);
                calculate = true;
            }

            while (sum > N && left < right) {
                sum -= primeNumbers.get(left++);
            }

            if (sum == N) {
                sum -= primeNumbers.get(left++);
                answer += 1;
            }

            if (!calculate)
                break;
        }

        System.out.println(answer);
    }

    private static List<Integer> getPrimeNumbers() {
        boolean[] num = new boolean[MAX_VALUE + 1];
        List<Integer> list = new ArrayList<>();

        // [문제점 2] 소수 생성 로직 오류
        // 1. Math.sqrt까지만 돌면, 그보다 큰 소수는 list에 담기지 않음 (list.add가 루프 안에 있음)
        // 2. 내부 루프 int j = i 부터 시작하므로 자기 자신(i)도 지워버림 (num[i] = true)
        for (int i = 2; i <= (int) Math.sqrt(MAX_VALUE); i++) {
            if (num[i]) continue;

            list.add(i);
            for (int j = i; j <= MAX_VALUE; j += i) {
                num[j] = true;
            }
        }
        // sqrt 이후의 소수들은 아예 list에 추가되지 않은 상태로 리턴됨

        return list;
    }
}

2. 정답 코드 (Refactored)

로직을 깔끔하게 정리한 최종 코드입니다.

// 성공
class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static List<Integer> primeNumbers;
    static final int MAX_VALUE = 4_000_000;
    static int N;
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        // 1. 전처리: 소수 리스트 생성
        primeNumbers = getPrimeNumbers();

        // 2. 투 포인터 탐색
        int left = 0;
        int right = 0;
        int len = primeNumbers.size();
        int sum = 0;

        while (true) {
            // 조건 분기 순서 중요: 
            // 1. sum이 N보다 크거나 같으면 left를 줄여야 함 (같을 때도 줄여서 다음 케이스 찾음)
            if (sum >= N) {
                sum -= primeNumbers.get(left++);
            } 
            else if (right == len) {
                // 2. sum < N인데 더 이상 더할 숫자가 없으면 종료
                break;
            } 
            else {
                // 3. sum < N이면 right를 늘려 합을 키움
                sum += primeNumbers.get(right++);
            }

            // 정답 체크
            if (sum == N) {
                answer += 1;
            }
        }

        System.out.println(answer);
    }

    // 에라토스테네스의 체 구현
    private static List<Integer> getPrimeNumbers() {
        boolean[] prime = new boolean[MAX_VALUE + 1];
        
        // 0과 1은 소수가 아님 (true: 소수 아님, false: 소수)
        prime[0] = prime[1] = true;

        List<Integer> list = new ArrayList<>();

        // 제곱근까지만 반복하며 배수들을 지움
        for (int i = 2; i * i <= MAX_VALUE; i++) {
            if (prime[i]) continue; // 이미 지워진 수라면 패스

            // i*i 미만은 이미 이전 루프에서 지워졌으므로 i*i부터 시작
            // j += i 로 i의 배수들을 지워나감
            for (int j = i * i; j <= MAX_VALUE; j += i) {
                prime[j] = true;
            }
        }

        // 배열 전체를 순회하며 소수(false)인 값들을 리스트에 담음
        for (int i = 2; i <= MAX_VALUE; i++) {
            if (!prime[i])
                list.add(i);
        }

        return list;
    }
}

회고 및 배운 점

1. 실패 원인 분석: Implementation Detail의 부재

실패한 코드에서 가장 큰 문제는 에라토스테네스의 체 구현 미숙이었습니다.

  • Loop 범위 오류: Math.sqrt까지만 루프를 돌면서 그 내부에서 list.add를 수행했습니다. 이 경우 N\sqrt{N}보다 큰 소수들은 리스트에 담기지 않는 치명적인 버그가 발생합니다.
  • Self-Deletion: 내부 루프 for (int j = i; ...)에서 시작 값을 로 잡는 바람에, 소수 자기 자신을 지워버리는(prime[i] = true) 오류가 있었습니다. 이로 인해 소수 리스트가 정상적으로 생성되지 않았습니다.

2. 투 포인터의 간결화 (Code Clean-up)

처음 코드에서는 while 문 안에 calculate 플래그와 중첩 while을 사용하여 흐름을 따라가기 어려웠습니다. 정답 코드에서는 이를 단일 while(true) 루프와 if-else if-else 구조로 변경했습니다.

  • 복잡도 유지: left와 right는 각각 최대 (소수의 개수)번 이동하므로 선형 시간 복잡도를 보장합니다.
  • 가독성: sum >= N일 때 left 이동, sum < N일 때 right 이동이라는 대원칙을 먼저 세우고, 종료 조건(right == len)을 그 사이에 배치하여 로직을 단순화했습니다.
profile
이종찬
왜? 라는 질문이 사라질 때까지
이전 포스트

[백준] BOJ_17404 RGB거리 2

다음 포스트

[백준] BOJ_2143 두 배열의 합

0개의 댓글