프로그래머스 [Lv. 2] 우박수열 정적분 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(k, ranges):
    answer = []
    
    stack = []
    while k > 1:
        stack.append(k)
        if k % 2:
            k = k * 3 + 1
        else:
            k //= 2
    stack.append(1)
    
    lenS = len(stack)
    areas = []
    for i in range(lenS-1):
        left = stack[i]
        right = stack[i+1]
        left, right = min(left, right), max(left, right)
        area = round((right - left) / 2, 1) + left
        areas.append(area)   
    
    dpA = [0 for _ in range(lenS)]
    dpA[1] = areas[0]
    for j in range(2, lenS):
        dpA[j] = dpA[j-1] + areas[j-1]
    
    for sr, er in ranges:
        if sr == 0 and er == 0:
            answer.append(dpA[-1])
        else:
            if sr > lenS+er-1:
                answer.append(-1)
            else:
                tmp = dpA[lenS+er-1] - dpA[sr]
                answer.append(tmp)

    return answer

풀이 방법

1. 우선 k를 나누고 곱한 뒤 x좌표를 만들어서 stack에 넣는다.
   1. 마지막에 1을 넣는 이유는 1이 되었을 때 while이 종료되기 때문이다.
2. 구간별 넓이를 구해서 areas에 차곡차곡 넣는다.
3. 구간합을 구할 때 인덱싱으로 자른다음에 sum으로 구하는 방법도 있지만
   1. 메모이제이션을 사용해서 미리 누적합을 구한다음에 용도에 맞게 빼서 구간합을 구한다.
   2. 예를 들어 [1, 2, 3, 4]가 있다면 dp = [0, 1, 3, 6, 10] 이 되고 [0, 4] = 10 - 0 = 10이 된다.
4. 이후 구간 합을 구할 때
   1. 중간에 sr보다 er이 큰 경우 -1을 append한다.
5. answer가 완성되면 return 한다.

느낀점

• 처음에 어떻게 구하지 생각했는데 그냥 처음부터 끝까지 넓이를 만든 뒤 더해주면 된다는 것을 깨달았다.