[Programmers/파이썬] 프로그래머스(Lv.2) 우박수열 정적분 문제풀이

문제 설명

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

프로그래머스

 

 

사고 흐름

1. 우선 우박수를 구해야겠다

2. 구한 우박수를 이용해서 넓이를 구해야하는데, k와 ranges의 최대 길이가 만개인데 매번 넓이를 구할 수는 없을 것 같다. 미리 넓이를 계산하자 -> DP

 

문제 핵심과 알고리즘

다이나믹 프로그래밍 (DP)

def solution(k, ranges):
    lc = []
    area = [0]
    res = []
    
    # lc - 우박수 생성 
    while k>1 :
        lc.append(k)
        if k%2==0 :
            k//=2
        else :
            k=k*3+1
    lc.append(1)
    
    # area: 정적분을 위한 누적 넓이 
    t = 0
    for i in range(len(lc)-1) :
        t+=(lc[i]+lc[i+1])/2
        area.append(t)
    
    # res: 정적분 
    n = len(lc)-1
    for r in ranges :
        a,b = r[0], n+r[1]
        if a>b :
            res.append(-1.0)
        else :
            res.append(area[b]-area[a])
            
    return res

 

우선 우박수를 구한 lc를 사용해서 누적 넓이를 구할 것이다. 누적 넓이를 계산하는 이유는 정적분 계산이 누적 넓이의 뺄셈으로 쉽게 구할 수 있기 때문이다. 그리고 ranges를 돌면서 범위에 맞는 정적분을 한다.

 

문제 풀면서 헤맸던 부분

없었다

 

총평 

(소요시간: 20분) 딱히 어려운 구현은 없었다. 하지만 문제가 좀 길고 과정이 좀 길어서 차분하게 단계를 정리하고 코드를 짜면 쉬운 문제이다. 그리고 k와 ranges의 크기를 보고 이건 매번 넓이를 계산할 수 없겠다 라고 판단하고 미리 계산하자! 고 방향을 빠르게 잡는게 핵심이다.