Level 2. 숫자의 표현

Level 2. 숫자의 표현

 

 

첫 번째 시도에서는 정답이었으나 시간 초과가 발생했다.

 

DP를 통해 간단하게 각 수까지의 합을 구했으나, 모든 경우의 수를 확인해서 그런 것 같다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>

using namespace std;

int solution(int n)
{
    int answer = 0;
    vector<int> sum(n + 1, 0);

    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + i;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < n; ++j)
            if (sum[i] - sum[j] == n)
                ++answer;

    return answer;
}

 

각 수부터 n보다 작은 동안만 더해 시간 초과를 해결했다.

 

#include <iostream>

using namespace std;

int solution(int n)
{
    int answer = 0;

    for (int i = 1; i <= n; ++i)
    {
        int sum = 0;

        for (int j = i; sum < n; ++j)
            if ((sum += j) == n)
                ++answer;
    }

    return answer;
}