[Programmers] Lv2. 우박수열 정적분 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

다음 문제 지문 부분이 무슨 말인지 헷갈려, 이해하는 데에 시간이 좀 걸렸습니다.

"단, 우박수열 그래프의 가로축 길이를 미리 알 수 없기 때문에
구간의 시작은 음이 아닌 정수, 구간의 끝은 양이 아닌 정수로 표현합니다.
이는 각각 꺾은선 그래프가 시작하는 점과 끝나는 점의 x좌표에 대한 상대적인 오프셋을 의미합니다."

 

구한 우박수열의 마지막 좌표(위 예제로 보면 (5, 1))의 x값을 LX라고 한다면, 주어진 구간 [a, b]는 [0 + a, LX + b]를 의미하는 거였습니다.

 

 

예를 들어, 위 예제에서 LX는 5입니다. (5, 1)이 마지막 우박수열 좌표이기 때문이죠.

• range가 [0, 0]으로 주어졌다면, [0 + 0, 5 + 0]이므로 [0, 5]인 전체 구간을 의미합니다.
• range가 [0, -1]로 주어졌다면, [0 + 0, 5 - 1]이므로 [0, 4] 구간 넓이를 구하면 됩니다.
• range가 [2, -3]으로 주어졌다면, [0 + 2, 5 - 3]이므로 [2, 2] 구간 넓이를 구하면 됩니다.
• range가 [3, -3]으로 주어졌다면, [0 + 3, 5 - 3]이므로 [3, 2]입니다. 잘못된 구간이므로 -1입니다.

 

x가 실수 영역이 아닌 정수 영역이기에, 정적분 넓이는 사다리꼴 형태로 나타나게 됩니다.

 

각 노란색 빗금 친 영역의 넓이를 구하면 됩니다.

 

x가 0부터 우박수열의 마지막 x값까지의 각 사다리꼴 넓이를 누적해서 저장한 후, 주어진 range에 의해 구해진 구간 [a, b]에 대해, \( f(b) - (a)\)의 넓이를 구해주면 됩니다.

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> cummulativeSum { 0.0 };
    
    while (true) {
        int nextK = (k % 2 == 0) ? k / 2 : (k * 3) + 1;
        double area = static_cast<double>(k + nextK) / 2;
        cummulativeSum.emplace_back(cummulativeSum.back() + area);
        k = nextK;

        if (k == 1)
            break;
    }
    
    vector<double> answer;

    for (const auto& range : ranges) {
        int leftX = range[0], rightX = cummulativeSum.size() - 1 + range[1];

        if (rightX < leftX) {
            answer.emplace_back(-1.0);
            continue;
        }

        double area = cummulativeSum[rightX] - cummulativeSum[leftX];
        answer.emplace_back(area);
    }

    return answer;
}