[Programmers] 숫자의 표현

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

프로그래머스

문제 설명

10000 이하의 자연수 n이 주어진다. 연속된 자연수의 합으로 n을 만들 수 있는 경우의 수를 구해야 한다. 간단하게 푸는 방법은 이중 for 문으로 해결하는 방법이다. 해결 후 다른 사람의 풀이를 보니 정수론에서 정리된 법칙을 이용해 for 문 한 번만으로 해결한 코드도 있었다. 주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있다고 한다. 이래서 수학 잘하면 좋나보다.

코드

class Solution {
    public int solution(int n) {
        // 자기 자신은 항상 포함되므로 1로 시작한다.
        int answer = 1;
        
        // 자신의 절반보다 큰 수와의 합은 항상 자신보다 크므로
        // n의 절반까지만 탐색하여 연산 횟수를 줄인다.
        for (int i = 1; i <= n / 2; i++) {
            int sum = i;
            for (int j = i + 1; j <= n; j++) {
                sum += j;
                if (sum > n) break;
                if (sum == n) answer++;
            }
        }
        
        return answer;
    }
}