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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int> GetCollatz (int k){
    vector<int> sequence {k};
    
    while(k > 1){
        k = (k % 2 == 0) ? k / 2 : k * 3 + 1;
        sequence.push_back(k);
    }
    
    return sequence;
}

vector<double> GetArea(const vector<int> &sequence){
    vector<double> areas(sequence.size() - 1);
    
    for(int i=0; i<sequence.size()-1; i++){
        double height1 = sequence[i];
        double height2 = sequence[i + 1];
        areas[i] = (height1 + height2) * 0.5;
    }
    
    return areas;
}

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    vector<int> sequence = GetCollatz(k);
    vector<double> areas = GetArea(sequence);
    int n = areas.size();
    
    for(int i=0; i<ranges.size(); i++){
        double area = 0.0;
        int a = ranges[i][0];
        int b = n + ranges[i][1];
        
        if(a > b){
            answer.push_back(-1.0);
        }else{
            for(int j=a; j<b; j++){
                area += areas[j];
            }
            
            answer.push_back(area);
        }
    }
    
    return answer;
}

---

📝 풀이

먼저 GetCollatz 함수를 이용하여 우박수열을 구합니다.

구한 우박수열을 이용하여 GetArea 함수로 각 구간의 넓이를 구합니다.

구간의 넓이는 가로가 1로 고정된 직삼각형의 넓이를 구합니다.

문제에 주어지는 범위를 시작과 끝 인덱스로 변환한 뒤 각 구간의 넓이를 더하여 정적분을 구합니다.

단 시작 인덱스가 끝 인덱스보다 커서 유효하지 않은 경우는 -1로 정의합니다.

최종적으로 answer을 반환합니다.