[오늘의 문제] 숫자의 표현

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12924

문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항
n은 10,000 이하의 자연수 입니다.
입출력 예
n result
15 4
입출력 예 설명
입출력 예#1
문제의 예시와 같습니다.

※ 공지 - 2022년 3월 11일 테스트케이스가 추가되었습니다.

내가 작성한 코드문

class Solution {
    public int solution(int n) {
        int count = 0;      // 정답: n을 연속된 수의 합으로 나타내는 방법의 수
        int sum = 0;        // 현재 구간의 합
        int start = 1;      // 구간 시작 숫자

        for (int end = 1; end <= n; end++) {
            sum += end;     // 1부터 n까지 끝 숫자 누적

            // 만약 합이 너무 크면 → 시작 숫자를 줄여서 합을 작게 만든다
            while (sum > n) {
                sum -= start;
                start++;
            }

            // 만약 합이 딱 n이 되면 카운트 추가
            if (sum == n) {
                count++;
            }
        }

        return count;
    }
}

다른 사람의 풀이

public class Expressions {

    public int expressions(int num) {
        int answer = 0;
   for (int i = 1; i <= num; i += 2) 
       if (num % i == 0) 
           answer++;

   return answer;
    }

    public static void main(String args[]) {
        Expressions expressions = new Expressions();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(expressions.expressions(15));
    }
}

💡 즉, num을 나눌 수 있는 "홀수 약수"의 개수를 구함 → 그것이 바로 정답!

자연수 num을 k개의 연속된 자연수의 합으로 표현한다고 하면:

num = k m + (k (k - 1)) / 2
(m은 시작 숫자)

여기서 정리하면:

num = k * (m + (k - 1)/2)

즉, k가 num을 나눌 수 있어야만 가능하며,
특히 이때 m이 자연수가 되어야 하므로 k는 반드시 홀수여야 자연수 m이 나온다.

🔹 즉, num을 연속된 자연수들의 합으로 표현 가능한 경우의 수 = num의 홀수인 약수 개수

public class Expressions {

    public int expressions(int num) {
        int answer = 0;

    int sum;
    for(int i = 1 ; i <= num ; i++) {
      sum = 0;
      for(int j = i ; j <= num ; j++) {
        sum += j;
        if(sum == num) {
          answer++;
          j = num+1;
        }
      }
    }

        return answer;
    }

    public static void main(String args[]) {
        Expressions expressions = new Expressions();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(expressions.expressions(15));
    }
}

✅ 이중 for문을 통한 연속합 탐색
i는 시작 숫자 (start)

j는 끝 숫자 (end)

i부터 j까지 합쳐서 sum을 만들고,

sum == num이면 경우의 수 1개 추가 (answer++)

sum > num이면 더 이상 검사하지 않고 탈출

✅ 성능 비교

방식	시간복잡도	특징
이 코드 (브루트포스)	O(n²)	단순하고 직관적이지만 느림
투 포인터	O(n)	효율적이며 논리적
홀수 약수 (수학 풀이)	O(√n)	매우 빠름 (단 수학적 아이디어 필요)