def solution(k, ranges):
    answer = []
    graph = []
    n = 0
    while k > 1 :
        temp = k
        if k % 2 == 0 : 
            k = k//2
        else :
            k = k*3 + 1

        a = max(temp, k)
        b = min(temp, k)

        graph.append(a - (a-b)/2)
        n += 1
    for i in ranges :
        count = 0
        if(len(graph)+i[1] >= i[0]) :
            for j in graph[i[0]:len(graph)+i[1]]:
                count += j
        else : count = -1
        answer.append(count)
    return answer

• 문제정리

  숫자 k와 범위 range가 주어졌을 때, 범위 내의 정적분(넓이)를 구하는 문제입니다.

  숫자 k는 콜라츠 추측에 의해 y값을 구하는데 사용됩니다.

  콜라츠 추측, 처음의 n이 짝수면 % 2 홀수면 * 3 + 1 → 계속반복하면 1이됨

  즉 x는 콜라츠 추측 한번할때마다 + 1, y는 위의 반복으로 정해지며

  → 1이 될때까지의 그래프를 구한후 구간별로 정적분하여 넓이를 구하는 문제

• 풀이과정

  y가 구간별로 달라지며 구간별로 그래프의 기울기가 달라지기(1차 함수)때문에 구간별로 넓이를 구해놓고 range에 따라 넓이를 더하여 계산해주는 과정을 통해 풀이하였다.

  시간복잡도를 고려하여 넓이를 구하는 반복을 따로 하지않고 콜라츠 추축으로 y값을 구할때마다 바로바로 넓이를 구해 graph배열에 추가하였고

  다음에 range를 순회하며 graph에서 값을 찾아 값을 더해주며 answer에 추가해주었다.

• 풀이 후

  크게 다른거같지는 않은데 dp로 풀은 문제가 눈에 띄었다.