[프로그래머스] 연속된 수의 합 (C++)

연속된 수의 합 / Lv.0

---

문제  설명 )

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

 

 

 

제한 사항 )

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

 

 

 

입출력 예 )

 

 

입출력 예 설명 )

입출력 예 #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

• 설명 생략

 

 

풀이)

 

#include <string>
#include <vector>
#include <numeric>
#include <deque>
 
using namespace std;
 
vector<int> solution(int num, int total) {
    vector<int> answer;
    
    // -total 부터 num만큼 숫자를 더해 브루트 포스
    int temp = total * -1;
    
    // 양방향 자료구조를 사용
    deque<int> d;
    // num의 개수만큼 temp부터 삽입
    for(int i = 0; i < num; i++)
    {
        d.push_back(temp);
        temp++;
    }
    
    // total이 될 수 있는 케이스가 나올때까지 반복
    while(1)
    {
        // numeric STL의 accumulate 사용
        // 배열의 합을 구해준다. (3번째 인자는 초기 값)
        int acc = accumulate(d.begin(), d.end(), 0);
        // 만약 조건에 부합한다면 멈춤
        if(acc == total) break;
        // 합이 total보다 작다면 뒷부분을 추가
        else if (acc > total)
        {
            d.pop_back();
            d.push_front(d.front() - 1);
        }
        // 합이 total보다 크다면 앞부분을 추가
        else if (acc < total)
        {
            d.pop_front();
            d.push_back(d.back() + 1);
        }
    }
    
    // 정답 배열에 넣어준다.
    for(int i = 0; i < d.size(); i++)
    {
        answer.push_back(d[i]);
    }
    
    return answer;
}

---

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120923

프로그래머스