우박수열 정적분

프로그래머스

 

 

DP 테이블을 활용해서 풀 수 있는 문제.

 

---

풀이 코드

def solution(k, ranges):
    result = []
    
    arr = [k] # arr[i] = i번째 값
    n = 0 # 작업 횟수
    while k > 1:
        if k % 2 == 0:
            k //= 2
        else:
            k = k * 3 + 1
        n += 1
        arr.append(k)
        
    dp = [0] * (n + 1) # dp[i] = [0, i]까지의 정적분 결과를 저장하는 dp 테이블
    
    # 정적분 결과를 dp 테이블에 저장
    for i in range(n):
        small_y = min(arr[i], arr[i+1])
        big_y = max(arr[i], arr[i+1])
        
        current_area = small_y * 1 + (big_y - small_y) * 1 * 0.5
        dp[i+1] = dp[i] + current_area
    
    
    # 각 범위에 대해
    for a, b in ranges:
        if n + b == a: # 시작점과 끝점이 같은 경우 넓이는 0
            result.append(0.0)
        elif n + b < a: # 시작점이 끝점보다 큰 경우 유효하지 않은 구간이므로 -1
            result.append(-1.0)
        else: # 그 외에는 정적분 결과 리턴
            temp_result = dp[n+b] - dp[a]
            result.append(temp_result)
            
    return result