[프로그래머스/C++ 문제 풀이] Lv. 0 - 연속된 수의 합

문제 설명

연속된 세 개의 정수를 더해 12가 되는 경우는 3, 4, 5입니다. 두 정수 num과 total이 주어집니다. 연속된 수 num개를 더한 값이 total이 될 때, 정수 배열을 오름차순으로 담아 return하도록 solution함수를 완성해보세요.

제한 사항

• 1 ≤ num ≤ 100
• 0 ≤ total ≤ 1000
• num개의 연속된 수를 더하여 total이 될 수 없는 테스트 케이스는 없습니다.

입출력 예

num	total	result
5	15	[1, 2, 3, 4, 5]
4	14	[2, 3, 4, 5]
5	5	[-1, 0, 1, 2, 3]
3	12	[3, 4, 5]

 

 

입출력 예 #1

• num = 3, total = 12인 경우 [3, 4, 5]를 return합니다.

입출력 예 #2

• num = 5, total = 15인 경우 [1, 2, 3, 4, 5]를 return합니다.

입출력 예 #3

• 4개의 연속된 수를 더해 14가 되는 경우는 2, 3, 4, 5입니다.

입출력 예 #4

• 설명 생략

---

문제 풀이

이번 문제는 num개의 연속된 수의 합이 result가 되는 시작 숫자를 구하는 것이 중요한 문제입니다.

 

수학적으로 생각해보면 공차가 1인 등차 수열의 합 공식을 이용해 풀 수 있지만...

해당 공식을 까먹었던 저는 점화식을 만들기 위해 많은 시간을 쏟았고,,, 결국 검색을 하여 공식을 찾게 되었습니다.

 

공식을 쉽게 설명하기 위해 등차수열 1, 2, 3, 4, 5.... 10을 이루는 항이 있다고 가정하고, 합을 구해보도록 하겠습니다.

S = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
S = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

 

위와 같이 더할 수 있으며, 두 식을 더해보면 다음과 같은 값이 나오게 됩니다.

2S = 11 + 11 + 11 .... + 11

 

즉, 11 * 10 = 110 = 2S가 되며, S = (11 * 10) / 2인 것을 확인할 수 있습니다.

 

이제 등차수열로 넘어오도록 하겠습니다.

첫째항이 a, 공차가 d인 등차수열의 n번째 항은 a + (n - 1)d입니다.

 

처음 S를 구했던 것처럼 한 번 더해보도록 하겠습니다.

Sn = a + (a + d) + (a + 2d) + ... + (a + (n - 2)d) + (a + (n - 1)d)
Sn = (a + (n - 1)d) + (a + (n - 2)d) + ... + (a + 2d) + a

2Sn = (2a + (n - 1)d) + (2a + (n - 1)d) + (2a + (n - 1)d) + ... + (2a + (n - 1)d) 이 될 것입니다.

 

위와 같은 상황에서 (2a + (n - 1)d)는 n개 존재하므로, 2Sn = n(2a + (n - 1)d) 과 같이 정리가 가능합니다.

 

위 공식과 함께 문제로 돌아와보면

Sn = Total , n = num , d = 1 인 것을 쉽게 알 수 있습니다.

 

그렇다면 해야 할 일은 첫 항인 a를 구하는 일이므로 이제는 어렵지 않습니다.

a만 남기고 모든 항을 전부 넘겨준다면?

 

> (2Sn/n - (n - 1)d) / 2 = a 이므로, 다음과 같은 점화식을 만들 수 있습니다.

(2 * total / num - num + 1) / 2 = Start

정답 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int num, int total) {
    vector<int> answer;

    // 등차수열의 합 공식 이용하기
    // * S : 1~n항 까지의 합
    // * a : 첫째 항
    // * d : 공차
    //   => Sn = n(2a + (n - 1)d) / 2
    //   => (2Sn/n - (n - 1)d) / 2 = a
    //   => (2 * total / num - num + 1) / 2 = Start

    // 즉, 공식대로 시작 항(Start)을 구해 num만큼의 수를 결과값에 집어넣어 해결합니다. 
    int Start = ((2 * total / num) - num + 1) / 2;

    for (int i = Start; i < Start + num; i++)
    {
        answer.push_back(i);
    }

    return answer;
}