문제 출처

1. 문제설명

  • 콜라츠 추측이란 모든 자연수 k에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측이다.

    1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.
  • 콜라츠 추측을 이용해 좌표 평면 위에 꺾은선 그래프를 나타내려고 한다.
    • 초항이 k라면, x = 0일때 y = k이고 다음 항은 x = 1에 표시
    • 5를 콜라츠 추측하면 0번째 위치부터 y 값은{5, 16, 8, 4, 2, 1}이 된다.
  • 이렇게 만들어진 그래프에서 구간이 주어질 때 정적분의 결과를 구하라
    • 시작점이 끝점보다 커서 유효하지 않다면 -1로 정의


2. 입/출력

  • 입력
    • 우박수의 초항 k
    • 정적분을 구하는 구간들의 목록 ranges
  • 출력
    • 정적분의 결과 목록을 return


3. 문제 분류

  • Simulation, Math(?)


4. 알고리즘 설계

  • 5의 우박 수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1이 된다.
  • 향후 계산을 위해 {i, i번째 우박수열} 형태로 저장한다.
  • 각 구간 탐색
    • [s, -e]라면 1번째부터 뒤에서 2번째까지라는 의미이다.
    • 인덱스로 접근하기 위해 수열의 크기 - 1 + -e가 되겠다.
    • 이 때 s > e크다면 문제에서 언급한 -1이 될 것이다.
    • 그렇지 않다면, s부터 e까지
      • i번째 y와 i+1번째 y를 더해 2로 나눈 값을 더한다.


5. 전체 코드

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

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    vector<pair<int,int>> v;
    v.push_back({0, k});
    
    for(int i = 1; k != 1; i++) {
        if(k % 2) k = k * 3 + 1;
        else k /= 2;
        v.push_back({i, k});
    }
    
    for(auto nxt : ranges) {
        int s = nxt[0];
        int e = v.size() - 1 + nxt[1];
        
        if(s > e) answer.push_back(-1.0);
        else {
            double res = 0.0;
            for(int i = s; i < e; i++)
                res += (double)(v[i].second + v[i+1].second) / 2;
            answer.push_back(res);
        }
    }
    
    return answer;
}


6. 소감

  • 구간의 크기가 1이라면 그 구간의 모양은 사다리꼴이 된다.
    • 규칙에 의해 이전 수와 같은 수가 될 수 없기 때문이다.
  • 사다리꼴의 너비를 구하는 방법을 확실하게 알지 못했는데, 예제를 통해 유추할 수 있었다.
  • 알고리즘 문제를 보면 수학적 지식을 이용하는 문제들이 많이 있다.
    • 가끔 이게 무슨 말인지 싶은 문제들도 있는데…
    • 다양한 문제를 풀어보고 얼른 습득하도록 노력해야겠다.