[programmers/py] 우박수열 정적분

우박수열 정적분

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

문제 설명

콜라츠 추측
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.

예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.

수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다.

예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

풀이 설명

1. 우박 수열을 구합니다.
2. 각 점마다 넓이를 구합니다.
3. 계산

def solution(k, ranges):
    answer = []
    
    # 우박 수열을 구한다.
    arr = []
    cnt = 0
    while k != 1:
        arr.append(k)
        if k % 2 == 0:
            k //= 2
        else :
            k = k*3+1    
        cnt += 1
    arr.append(k) # k==1인 경우
    
    N = len(arr)-1

    # 각 구역의 넓이
    area = []
    for i in range(N):
        small = min(arr[i], arr[i+1])
        a = small + abs(arr[i] - arr[i+1])/2
        area.append(a)
        
    for x,y in ranges:
        y = y if y>0 else N+y
        
        if x > y:
            answer.append(-1)
            continue
        s = 0
        for i in range(x,y):
            s += area[i]
        answer.append(s)
        
        
    return answer