연속된 수의 합, 등차 수열 응용

연속된 n개의 수의 합이 total이 되는 vector를 구하는 문제이다.

 

물론 나는 수열 공식 같은 거 몰라서 걍 풀었다.

 

#include <string>
#include <vector>
#include <numeric>

using namespace std;

vector<int> solution(int num, int total) {
    vector<int> answer(num);
    vector<int> numList(1050);
    iota(numList.begin(), numList.end(), -50);
    int i = (num >= total) ? 0 : 50;

    for (; i <= numList.size(); ++i)
    {
        int sum = accumulate(numList.begin() + i, numList.begin() + i + num, 0);

        if (sum == total)
        {
            copy(numList.begin() + i, numList.begin() + i + num, answer.begin());
            break;
        }
    }

    return answer;
}

 

• 등차수열의 합 공식을 이용한 풀이

1. 평균값: total / num은 num개의 연속된 정수의 평균값. (중앙값)

2. 시작 인덱스: 홀수: (num - 1) / 2, 짝수: num / 2 - 1

그러나, c++은 소숫점 이하를 버리기에 홀수 계산 법으로 홀/짝 관계 없이 시작 인덱스를 구할 수 있다.

 

vector<int> solution(int num, int total) {
    vector<int> answer(num);
    int start = (total / num) - ((num - 1) / 2); // 시작 인덱스 계산

    for (int i = 0; i < num; ++i) {
        answer[i] = start + i;
    }

    return answer;
}