숫자의 표현

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

이 문제는 시간복잡도를 고려해 주어야한다.
특히 이중포문으로 완전탐색을 하는 경우 효율성 측면에서 모두 실패가 나온다.

핵심 아이디어
(1) 연속된 수의 합을 더하는 경우, 주어진 n값의 절반값보다 큰 수들을 연속으로 더하면 무조건 n값보다 커지게 된다. 이 아이디어를 떠올리고 탐색의 조건을 n/2까지 두어 시간복잡도를 줄인다.

(2) 기준값을 잡고, 그 기준값에 모든 수를 더할 필요 없이, n보다 작을때까지만 더해준다. 불필요한 더하기를 낭비하지 않을 수 있다.

(3) 최종적으로 자기 자신을 더해주어야 한다. 왜? 탐색을 하는 경우 n/2까지 밖에 탐색을 해주지 않았으므로!

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int k = 1; k <=n/2; k++) { // (1)번 아이디어
            int i = k;
            int sum = 0;

            while(sum < n){ // (2)
                sum += i++;
            }

            if(sum == n){
                answer++;
            }
        }
        
        answer+=1; // 
        
        return answer;
    }
}