프로그래머스 - 연속된 수의 합 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(int num, int total) {
    vector<int> answer;
    int arr[101]={0,};
    int a = total / num;
    
    while(true)
    {
        int sum = 0;
        for(int i=0;i<num;i++)
        {
            sum+=a-i;
            arr[i]= a-i;
        }
        if(sum==total)
        {
            for(int i=0;i<num;i++)
                answer.push_back(arr[i]);
            sort(answer.begin(),answer.end());
            break;
        }
        a++;
    }
    return answer;
}

 

설명

이 문제는 num개의 연속된 숫자들로 그 합을 total로 만들 수 있는 숫자들을 반환해주는 문제이다.

예시를 보니 total/num 인 수가 양 끝에오는 경우는 존재하지 않고 그 사이에 존재하였다. 

따라서 total / num 인 수를 가장 큰 수로 가정하고 total과 비교하며 total 보다 +1 큰수를 하나씩 추가해가며 

total과 같아졌을 때를 찾는다. 

 

1. total/num 인 수를 가장 크다고 가정한다.

int a = total / num;
    
    while(true)
    {
        int sum = 0;
        for(int i=0;i<num;i++)
        {
            sum+=a-i;
            arr[i]= a-i;
        }

총 숫자의 개수는 num개니까 for문은 num까지 돈다. 

a - i 를 하면 1씩 작아진다. 그 시작을 total / num 으로 한다. 

 

2. total과 같다면 그대로 그 숫자들을 리턴해준다. 

그렇지 않다면 a를 1 증가시킨다. 

if(sum==total)
        {
            for(int i=0;i<num;i++)
                answer.push_back(arr[i]);
            sort(answer.begin(),answer.end());
            break;
        }
        a++;

arr에는 0번인덱스부터 num개의 숫자가 들어가있다. 그것들을 answer에 삽입하고 sort함수로 오름차순 정렬시킨다. 

그리고 그렇지 않다면 a를 증가시켜서 total/num 보다 1 큰수를 다음 for문에 등장시킨다. 

 

ex) num = 3, total = 12 일 때

a = total/num = 4 이고 

처음엔 4+3+2 를 계산한다. total인 12보다 작기 때문에

a를 1 증가시킨다. 

다음엔 5+4+3을 계산한다. total과 동일하기 때문에 

answer에 5,4,3 을 넣고 오름차순정렬시킨다.

따라서 {3,4,5}가 리턴된다.