[PS] 숫자의 표현

문제

해결 - 1

보자마자 든 생각은 1부터 n까지 순회하면서 그 숫자부터 시작해서 하나씩 빼면서 0에 딱 맞는지 0보다 작은지 체크하면 되겠네! 였다.
1트만에 정답을 맞췄지만 찝찝했다. 최악의 경우 O(n^2)일 수 있기 때문에

소스코드 - 1

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for(int i=1;i<=n;++i)
    {
        int remain = n;
        for(int j=i;;++j)
        {
            remain -= j;
            if(remain == 0)
            {
                answer++;
                break;
            }
            else if(remain < 0)
            {
                break;
            }
        }
    }
    return answer;
}

해결 - 2

다른 사람의 풀이에서 본 풀이 하나가 신기해서 기록하려고 한다.

이 분은 연속된 수의 합을 다른 시각으로 해석했다.
연속된 수면 가장 앞에 있는 수를 반복되는 숫자로 해석하고, 그 숫자를 뒤에 있는 숫자들에서 뺀(여기서는 계단수 라고 하겠다) 계단수의 조합으로 표현했다.

k 개의 반복수가 a개 만큼 있고, 나머지 a개 숫자의 합으로 이루어진 계단수의 조합으로 해석했다.

소스코드 - 2

int solution(int n) {
    int answer = 0;
    int digit = 0;
    for(int i=0;i<=n;++i)
    {
        digit += i; // 계단수
        int share = n - digit; // K
        int div = i + 1; // alpha
        if(share >= div && share % div == 0) answer++;
    }
    return answer;
}