숫자의 표현

문제

자연수 n을 연속한 자연수들로 표현하는 방법의 수를 구하는 문제입니다. 예를 들어 15는 다음과 같이 4가지로 표현할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15
• 입력: 자연수 n (1 ≤ n ≤ 10,000)
• 출력: 연속된 자연수들로 n을 표현하는 방법의 수

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12924

풀이 1: 등차수열의 합 공식을 이용한 완전 탐색

"i부터 j까지의 연속된 수의 합 = (첫 항 + 끝 항) * 항의 개수 / 2" 공식을 활용한 방식입니다.

• 이중 반복문: 시작 숫자 i를 1부터 n까지 설정하고, 끝 숫자 j를 i부터 n까지 순회합니다.
• 합 공식 검사: (j + i) * (j - i + 1) / 2 값이 n과 일치하면 카운트(ans++)합니다.
• 조기 종료 (가지치기): 만약 공식으로 계산한 합이 목표인 n보다 커졌다면, j를 더 늘려봤자 무조건 n을 초과하게 되므로 내부 반복문을 즉시 중단(break)합니다.

코드 1

class Solution {
    public int solution(int n) {
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int sum = (j + i) * (j - i + 1) / 2;
                
                // 합이 정확히 n이면 방법의 수 증가
                if (sum == n) {
                    ans++;
                    break; // 더 이상 확인할 필요 없으므로 중단
                } 
                // 합이 n을 초과하면 더 이상 탐색하는 것이 무의미하므로 조기 종료
                else if (sum > n) {
                    break;
                }
            }
        }
        
        return ans;
    }
}

풀이 2: 투 포인터 (Two Pointers)를 활용한 O(N) 탐색

시작점(left)과 끝점(right)을 두고, 부분 수열의 합(sum)이 목표값 n보다 작으면 오른쪽으로 구간을 늘리고, 크면 왼쪽 구간을 줄여나가는 슬라이딩 윈도우/투 포인터 방식입니다.

• 배열 전체를 O(N)에 한 번만 훑기 때문에 속도가 매우 빠르고 직관적입니다.

코드 2

class Solution {
    public int solution(int n) {
        int ans = 0;
        int left = 1, right = 1, sum = 1;

        while (left <= n) {
            // 합이 n과 같으면 카운트 증가
            if (sum == n) {
                ans++;
            }
            
            // 합이 n보다 작거나 같으면 오른쪽으로 구간 확장
            if (sum <= n) {
                right++;
                sum += right;
            } 
            // 합이 n보다 크면 왼쪽 구간을 빼주면서 축소
            else {
                sum -= left;
                left++;
            }
        }
        
        return ans;
    }
}

알고리즘 분류

완전 탐색 (Brute Force), 투 포인터 (Two Pointers), 수학 (Mathematics)