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

문제 설명

예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/134239?language=cpp 

프로그래머스

제한 사항

• 2 ≤ k ≤ 10,000
• 1 ≤ ranges의 길이 ≤ 10,000
  • ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
• 주어진 모든 입력에 대해 정적분의 결과는 227 을 넘지 않습니다.
• 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.

입출력 예

k	ranges	result
5	[[0,0],[0,-1],[2,-3],[3,-3]]	[33.0,31.5,0.0,-1.0]

풀이

정적분(넓이)를 구하기 위해서 각 범위의 사다리꼴 넓이를 구해야 합니다.

- 사다리꼴 넓이 : ( (윗변 + 아랫변) * 높이 ) / 2

위 그래프에서는 y값을 윗변, 아랫변 값으로 지정하고, 높이는 x값이 됩니다.

x값은 1씩 증가하는 인덱스 값입니다.

첫번째 사다리꼴 넓이 = ((y0 + y1) * 1) / 2  입니다. 높이는 항상 1이므로 생략합니다.

 

5의 정적분 개수 cnt = 6입니다. (5, 16, 8, 3, 2, 1)

정적분 범위는 range[x, y] = [ 0 + x , cnt - y]  임을 알 수 있습니다.

ex) k = 5, range[1, -2] = [0+1, 6-2] = (1 <= x <=3) 구간입니다.

 

저는 정적분을 구하면서 사다리꼴의 넓이를 구하고, 넓이를 누적한 값을 사용하여 문제를 풀었습니다.

range[1, 0] → s = 1, e = 6 일 때, 정적분은  vec[e] - vec[s] 입니다. vec[e]에는 0~e범위까지 사다리꼴의 넓이가 저장되어 있고, vec[s]는 0~s 범위 까지의 사다리꼴 넓이가 저장되어 있습니다. 

그렇기 때문에 vec[e] - vec[s] 를 계산하면 1 <= x <= 6의 정적분 값을 구할 수 있습니다.

이런 원리를 이용한 문제 풀이입니다.

 

range x값은 0부터 나올 수 있으므로, 사다리꼴 넓이 누적 값의 처음 값은 0을 먼저 삽입합니다.

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

vector<double> solution(int k, vector<vector<int>> ranges) {
    double prev = k, curr = k, val = 0;
    vector<double> sumVec;
    sumVec.push_back(0);
    while( curr > 1){
        if( (int)curr % 2 == 1){
            curr = curr * 3 + 1;
        }
        else{
            curr /= 2;
        }
        val += (prev + curr) / 2;
        sumVec.push_back(val);
        prev = curr;
    }
    
    vector<double> answer;
    for(int i = 0; i < ranges.size(); i++){
        int s = ranges[i][0];
        int e = sumVec.size() -1 + ranges[i][1];
        double sum = 0;
        
        if(s == e){
            sum = 0;
        }
        else if(s > e){
            sum = -1;
        }
        else{
            sum = sumVec[e] - sumVec[s];
        }
        answer.push_back(sum);
    }
    return answer;
}