[프로그래머스 Level2] 숫자의 표현

📝 숫자의 표현

문제 설명

숫자의 표현

해결 방법

연속된 수들의 합으로 이루어진 조합을 찾아야 하는데 n의 중간값을 넘어간 연속된 수들을 더한 조합은 없다. 예를 들어서 n이 15라면 7 + 8은 되는데, 8 + 9의 조합으로 나타낼 수 없다는 뜻이다. 즉 반복의 범위가 제한된다. 홀수일 때를 고려해서 1부터 (n + 1) / 2 까지만 더한다. 연속된 수를 더한 값이 n이면 answer++하고 그 이상이면 1부터 차례대로 빼서 표현가능한 조합을 찾는다. n = n인 case도 존재하므로 answer는 1부터 시작했다. n = 1일 때 if문으로 예외처리를 해주었다.

💻소스코드

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 1, j = 1;
    int sum = 0;
    if (n == 1)
        return answer;
    for (int i = 1; i <= (n + 1) / 2; i++) {
        sum += i;
        if (sum >= n) {
            while (sum > n) {
                sum -= j;
                j++;
            }
            if (sum == n)
                answer++;
        }
    }
    return answer;
}