[프로그래머스-lv2] 우박수열의 정적분

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/134239

프로그래머스

---

문제 풀이)

 특정 알고리즘이 필요한 문제는 아니었다. 말이 정적분이지만 사실은 사다리꼴의 넓이를 구하는 공식만 아는 정도면 해결할 수 있었던 문제

 

사다리꼴의 넓이 = (윗변 + 아랫변) x 높이 / 2 ....

 

근데 뭐든 국어가 문제인것 같다. 문제에서 말하는 오프셋의 의미를 정확히 파악하면 바로 해결할 수 있는 문제였다.

문제에 써있다. 그래프가 끝나는 점으로부터의 오프셋 즉 우박수열의 길이에서부터의 변위차다.

즉 예를 들어 0,0 이 그래프 전체 넓이를 나타내는 이유는

0, 0  => x=0에서부터 (5 - 0) 이기 때문에 전체 넓이를 나타내는것

만약 0, -1 이라면 x=0에서부터 (5-1) 즉 0~4까지의 합을 나타내는것이다.

 

따라서 문제 풀이과정은 다음과 같다.

구간합 배열을 만들어 논다.

구간합의 i번쨰 인덱스는 0에서부터 구간 i까지 정적분의 결과값이 담겨있는 함수다.

이후에 ranges 리스트를 보면서 내가 구간합을 구해야 하는 범위가 a부터 b까지라고 하면

구간합[b] - 구간합[a]를 해주게 되면 a부터 b까지의 구간합을 구할수 있다.

def solution(k, ranges):
    answer = []
    sum_data = [0.0] # 구간합 배열
    while True:
        next = k * 3 + 1 if k % 2 != 0 else k // 2 # 다음 우박수
        sum_data.append(sum_data[-1] + (k + next) / 2) # 지금 구간에서의 합
        if next == 1: # k가 1이면 종료
            break
        k = next

    for a, offset in ranges:
        b = (len(sum_data) - 1) - (offset*-1)
        if a == b:
            answer.append(0.0)
        elif a < b:
            answer.append(sum_data[b] - sum_data[a]) #구간합 구하기
        else:
            answer.append(-1.0)
    return answer