[Python] 프로그래머스 / Summer/Winter Coding / 쿠키 구입

문제 링크

 

Simple is the best 

쫄지 말자. 구간합 문제는 누적리스트로 풀릴 때가 많다.

def solution(cookie):
    
    n = len(cookie)
    
    S = [0] * (n+1)
    
    for i in range(1, n+1) :
        S[i] = S[i - 1] + cookie[i - 1]
        #S[i]는 A[i-1]까지의 합
        
    max_sum = 0
    
    for m in range(n-1) :
        l = 0
        r = n-1
        
        while l<=m and m+1<=r :
            left = S[m+1] - S[l]
            #S[m+1]는 cookie[m]까지의 합
            #S[l]은 cookie[l-1]까지의 합
            
            right = S[r+1] - S[m+1]
            #S[r+1]는 cookie[r]까지의 합
            #S[m+1]은 cookie[m]까지의 합
            
            if left == right:
                max_sum = max(max_sum, left)
                break
                
            elif left > right :
                l += 1
                
            else :
                r -= 1
                
    return max_sum