[Python/파이썬] 프로그래머스 Lv2 - 우박수열 정적분

문제 설명

 

제한사항

 

입출력 예

 

---

Solution.py

초항 K가 5일 때 콜라츠 추측으로 계산하면 다음과 같은 수열이 나옵니다. [5, 16, 8, 4, 2, 1]

나온 수열 대로 그래프를 그려보면  아래와 같은 그림이 나옵니다.

여기서 각 꼭지점마다 선을 그어서 사다리꼴 사각형을 만들 수 있습니다.

여기서 기억나지 않는 사람들 위해 사다리꼴 사각형이란 무엇인지에 대해 설명하자면

평행한 변이 있는 사각형, 즉 마주 보는 한 쌍의 변이 서로 평행한 사각형을사다리꼴이라고 합니다.

이제 문제의 답을 구하기 위한 각 구간의 넓이를 구해야하는데

그림을 보면 사다리꼴 넓이로 구간의 넓이를 구할 수 있어 보입니다. 

각 사다리골 사각형들의 넓이를 구해 구간의 넓이를 구해 봅시다.

사다리꼴 넓이는 ((윗변+아랫변) * 높이) / 2 공식으로 구할 수 있습니다.

아래 그림을 참고하면 이 문제에 대해 쉽게 이해할 수 있을 겁니다.

 

정답 코드

def getUbak(k):
    result = []
    while k != 1:
        result.append(k)
        # 결과가 소수이므로 / 연산
        k = k / 2 if k % 2 == 0 else k * 3 + 1 
    result.append(k)
    return result

def solution(k, ranges):
    answer = []
    ubak = getUbak(k)

    for r in ranges:
        total = 0
        ubakRange = ubak[r[0] : len(ubak)+r[1]]
        
        # 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간
        if r[0] >= r[1] + len(ubak):
            answer.append(-1)
            continue
            
        for i in range(len(ubakRange) - 1):
            # 사다리꼴 넓이 구하는 공식 : ((윗변+아랫변) * 높이) / 2
            total += (((ubakRange[i] + ubakRange[i+1]) * 1) / 2)
        answer.append(total)
        
    return answer