[프로그래머스 2레벨] 우박수열 정적분 (C++)

#include <string>
#include <vector>

using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    vector<int>v;
    v.push_back(k);
    while(k!=1)
    {
        if(k%2) k = 3*k +1;
        else k/=2;
        v.push_back(k);
    }
    
    for(auto range : ranges)
    {
        int s = range[0];
        int e = v.size()-1 + range[1];
        
        double tmp = 0;
        for(int j=s; j<e; j++)
        {
            tmp += (double)(v[j] + v[j+1]) / 2;
        }
        
        if(s > e) answer.push_back(-1.0);
        else answer.push_back(tmp);
    }
    return answer;
}

 

우선 콜라츠 추측에 따른 k값을 담아준다.

이후 주어진 범위 값에 대해 시작점과 끝점을 저장해주어야 한다.

끝점의 경우 기존 콜라츠 추측을 통해 얻은 전체 갯수에서 주어진 범위값(음수)를 더해서 최종 끝점을 얻게 된다.

 

이제 넓이를 구해야하는데, 형태를 보면 처음 y좌표를 윗변, 다음 y좌표를 아랫변으로 하는 사다리꼴의 형태이다.

높이의 경우 인덱스 차이인 1이 된다.

이를 공식으로 보면 (윗변+아랫변)/2 가 된다.

여기서 윗변과 아랫변은 콜라츠 추측에서 담은 벡터의 처음값과 그 다음 값이므로, 주어진 시작점과 끝점 범위를 이용한 반복문을 통해 넓이를 계산한게 된다.

그리고 예외처리를 위해 시작점이 끝점 보다 큰 경우에는 -1.0을 담아주고 이외에만 계산한 값을 담아준다.