[프로그래머스 C++] 우박수열 정적분

[프로그래머스 C++] 우박수열 정적분

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

해결방안

수학, 구현

정적분 공식을 사용하지 않아도 된다.

구분구적법의 개념으로 x길이 1단위로 도형의 넓이를 구하면 된다.

넓이는 마름모를 구하는 방식인 (윗변 길이 + 아랫변 길이) / 2 로 구하면 된다.  

정답 코드

#include <vector>
using namespace std;
 
vector<double> solution(int k, vector<vector<int>> ranges) 
{
    vector<pair<int, double>> v; // (x, y) 좌표를 저장하는 벡터
	vector<double> answer;
 
    int n = 0;
    while (k > 1)
    {
        v.push_back({ n, k }); // (x, y) 좌표 저장
 
        if (k % 2 == 0){
            k /= 2;
        }
        else {
            k = k * 3 + 1;
        }
        n++;
    }
    v.push_back({ n, k });
 
    
    for(int i = 0; i < ranges.size(); i++) // 각 범위에 대해 넓이을 계산하고, 계산한 결과를 answer 벡터에 저장
    {
        double temp = 0.0f;
 
        if(ranges[i][0] > n + ranges[i][1]){ // 범위가 유효하지 않은 경우
            temp = -1.0f; // 문제에서 범위가 유효하지 않은 경우 -1를 넣으라함
        }
 
	    for(int j = ranges[i][0]; j < n + ranges[i][1]; j++)
        {
            temp += (v[j].second + v[j + 1].second) / 2;
	    }
        answer.push_back(temp);
    }
 
    return answer;
}
 
int main(){
    vector<vector<int>> testcase1 = { {0,0}, {0,-1}, {2,-3}, {3,-3} };
    vector<vector<int>> testcase2 = { {0,0}, {1,-2}, {3,-3} };
    
    vector<double> result1 = solution(5, testcase1);
    for(int i = 0; i < result1.size(); i++){
        cout << result1[i] << " ";
    }
    cout << "\n";
    vector<double> result2 = solution(3, testcase2);
    for (int i = 0; i < result2.size(); i++) {
        cout << result2[i] << " ";
    }
 
    return 0;
}