[프로그래머스 Lv. 2] 우박 순열 정적분

문제

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

접근

기하 문제와 누적 합

1) 콜라츠 추측을 구현하고 k에 맞는 y 좌표를 구한다. (x는 y좌표를 담은 리스트의 인덱스)

2) 현재 위치와 이전 좌표는 무조건 값이 다르기 때문에 구한 좌표들들은 무조건 사다리꼴 모양이 된다. 구한 좌표들로 사다리꼴 넓이를 구해 누적 합 방식으로 값을 저장한다.

3) ranges의 값으로 넓이 값을 구한 누적 합 리스트에서 가져온다.

Code

def solution(k, ranges):
    locations = []

    def make_Collatz(k):
        while True:
            locations.append(k)
            if k == 1:
                break

            if k % 2 == 0:
                k //= 2
            else:
                k = k * 3 + 1

    def trapezoid_area(up, down, height):
        return (up + down) * height / 2

    answer = []
    make_Collatz(k)
    max_x = len(locations)
    prefix_sum = [0] * max_x
    for i in range(1, max_x):
        prefix_sum[i] = prefix_sum[i - 1] + trapezoid_area(locations[i - 1], locations[i], 1)
    for a, b in ranges:
        if max_x + b - 1 < a:
            answer.append(-1)
        else:
            answer.append(prefix_sum[max_x  -1+ b] - prefix_sum[a])
    return answer

여담

간만의 알고리즘