우박수열 정적분과 DP

왜 정답률이 이거 밖에 안되지...? 싶을 정도로 쉬웠던 문제.
수학자들은 대단하고 수학은 신기하다.

콜라츠 추측은 로타르 콜라츠라는 독일의 수학자가 생각한 것인데, 어떤 수든 일정한 과정을 반복하면 1에 수렴할 것이라는 추측이다.

어떤 수가 짝수이면 2로 나누고, 홀수이면 3을 곱한 뒤 1을 더한다. 이 추측의 반례는 아직 나오지 않았고, 아마도 참일 것이라고 추정된다. 1해까지의 숫자를 넣어보았지만 모두 1에 도달했다고 한다. 전문 수학자부터 15살 중학생까지 증명에 수없이 도전했지만, 일반화부터 어려운 추측이라고 한다.

아무튼 추측은 이러하고, 우박수열 정적분 문제는 다음과 같다.

x축에는 시도한 횟수, y축에는 숫자가 들어간다. 총 횟수는 n으로 한다.
초항이 5인 우박수열은 [0, 5], [1, 16], [2, 8], [3, 4], [4, 2], [5, 0] 을 지나게 된다. 이 경우 n은 5이다.

그리고 정적분의 범위가 [a, b]로 주어지면 x가 a 이상 n+b 이하인 범위에서 정적분을 하면 된다. 보다시피 여러 개의 사다리꼴을 더하면 정적분의 크기가 나온다. 그래서 우리는 1씩 차이나는 x의 범위의 정적분을 저장하면 되는 것이다.

def solution(k, ranges):
    answer = []
    i = k
    n = 0
    cors = [(n, i)]
    spaces = []
    
    while i > 1:
        if i % 2 == 0:
            i = i // 2
        else:
            i = i*3 + 1
        n += 1
        cors.append((n, i))
    
    for i in range(len(cors)-1):
        spaces.append((cors[i][1]+cors[i+1][1])*1/2)

    for rang in ranges:
        nrang = [rang[0], n+rang[1]]
        
        if nrang[0] > nrang[1]:
            answer.append(-1)
        elif nrang[0] < nrang[1]:
            answer.append(sum(spaces[nrang[0]:nrang[1]]))
        else:
            answer.append(0)
    
    return answer

DP는 Dynamic Programming의 준말로, 부분 문제를 풀어야 하는 일이 반복될 때 그 때마다 일일이 부분 문제를 풀지 않고, 대신 부분 문제의 결과를 저장하여 전체 문제를 해결하는 알고리즘이다.

여기선 [0, 0]으로 범위가 주어지면, [0, 0]은 전체 정적분의 범위를 묻는 것이므로 전체를 일일이 다 계산하는 것이 아닌

[0,1]의 정적분 결과 + [1,2]의 정적분 결과 + [2,3]의 정적분 결과 + ... + [n-1, n]의 정적분 결과

이렇게 부분합끼리 계산을 하는 식으로 DP를 적용하면 된다.

끝!