프로그래머스 - 우박수열 정적분 (C++)

콜라츠 추측

 

---

 

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

프로그래머스

 

 이번 문제는 임의의 숫자 k가 주어졌을 때, k의 우박수열을 계산한 후 주어진 range의 정적분을 계산하는 문제이다. 우박수열을 계산하는 것은 매우 쉽다. 숫자가 짝수이면 2로 나누고 홀수일 경우 3을 곱한 후 1을 더하면 된다. 그렇기에 정적분에 대해 더 고민해야 한다. 간단히 얘기하자면 그래프의 밑 넓이를 구하면 된다.

 

하지만 문제의 예시 그래프를 봐도 알 수 있듯, 식이 단순하지 않은 것 같다. 그렇기에 일일이 적분 계산을 해야할 것이다.

 

계산해야 하는 영역

예를 들어 x가 0부터 5까지의 넓이를 계산한다고 해보자. 바로 계산하기에는 모양이 예쁘지가 않기에 구간을 나눠줄 필요가 있다.

 

구간을 5개로 나눌 수 있다.

위 그래프의 넓이의 총합은 위의 그림처럼 0 ~ 1, 1 ~ 2, 2 ~ 3, 3 ~ 4, 4 ~ 5인 구간들의 넓이의 총합이 될 것이다.

 

밑변이 1인 직사각형으로 나타낼 수 있다.

각 구간 중, x가 4 ~ 5일 때의 구간을 보자. 이 구간은 위의 그림처럼 밑변의 길이가 1이고 높이가 f(4) + f(5)인 사각형을 반으로 쪼갠 사각형이라 할 수 있다. 즉, 이 구간의 넓이는 (밑변 x 높이) / 2 = (1 x (f(4) + f(5))) / 2가 될 것이다. 그렇기에 만약 a ~ b 구간을 적분해야 한다면 a ~ a + 1, a + 1 ~ a + 2, ... b - 1 ~ b 구간들의 넓이의 총합을 계산하면 된다.

 

double Area(int startX, int endX)
{
    int gap = endX - startX;
    
    if (gap == 0)
        return 0.0;
    else if (gap == 1)
    {
        double y1 = graph[startX];
        double y2 = graph[endX];
        
        return (y1 + y2) / 2;
    }
    else
    {
        int midX = (startX + endX) / 2;
        
        return Area(startX, midX) + Area(midX, endX);
    }
}

 그리고 이것은 재귀를 통해 표현할 수 있다. 재귀는 같은 과정을 더 작게 쪼개면서 반복할 때 효과적이다. 그리고 이 과정 역시 특정 구간의 넓이를 쪼개면서 구해야 하기에 재귀가 적합하다 할 수 있다. 코드에서 gap은 구간의 길이, 즉 밑변의 길이이다. 밑변의 길이가 1일 경우 사각형 넓이를 반환하고 2 이상일 경우 두 영역으로 쪼갠 후 두 영역의 합을 반환한다. 그리고 위의 설명에서 언급하지 않은 부분으로 밑변의 길이가 0일 때를 따로 처리해주었다. 왜냐하면 2 ~ 2같이 같은 지점을 적분할 경우 밑변의 길이가 0이기에 넓이 역시 0이 된다. 하지만 이 부분을 따로 처리하지 않을 경우 에러가 발생하기에 명시적으로 처리하였다.

 

 아래는 모든 코드이다.

#include <string>
#include <vector>

using namespace std;

vector<int> graph;

double Area(int startX, int endX)
{
    int gap = endX - startX;
    
    if (gap == 0)
        return 0.0;
    else if (gap == 1)
    {
        double y1 = graph[startX];
        double y2 = graph[endX];
        
        return (y1 + y2) / 2;
    }
    else
    {
        int midX = (startX + endX) / 2;
        
        return Area(startX, midX) + Area(midX, endX);
    }
}

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    
    // 우박수열을 계산하는 부분
    int lastX = 0;
    int y = k;
    
    while(y > 1)
    {
        graph.push_back(y);
        
        if (y % 2 == 0)
            y /= 2;
        else
            y = (y * 3) + 1;
        
        ++lastX;
    }
    
    // 마지막 (lastX, 1)의 y값은 push되지 않았기에 따로 처리
    graph.push_back(y);
    
    for (int i = 0; i < ranges.size(); ++i)
    {
        vector<int> range = ranges[i];
        
        int startX = range[0];
        int endX = lastX + range[1];
        
        if (startX > endX)
            answer.push_back(-1);
        else
        {
            double area = Area(startX, endX);
            answer.push_back(area);
        }
    }
    
    
    return answer;
}