숫자의 표현

문제정의

---

한 자연수에 대해 연속한 자연수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

public class ExpressNum {

    //프로그래머스 문제풀이 level2 숫자의 표현
    public static void main(String[] args) {
        int n = 15;
        int answer = 0;
        int add = 1, sub = 1, sum = 0;
        while(add <= n)
        {
            sum += add++;
            while(sum > n)
            {
                sum -= sub;
                sub++;
            }
            if(sum == n)
                answer++;
            
        }
        System.out.println(answer);
    }
    
}

자칫 경우의 수가 많아 보일 수 있지만 생각해보면 연속한 숫자라는 것이 도움이 된다. 1부터 차례대로 더해가며 n에 딱 맞을 경우 answer를 늘려주면 되고, 만약 n을 초과했다면 뒤에서부터 작아지거나 같아질 때까지 빼주면 된다.

최종 시간복잡도는 숫자를 빼고 더하는 최대 횟수가 2n이므로 \(O(n)\)이다.

테스트