프로그래머스 - 쿠키구입

https://programmers.co.kr/learn/courses/30/lessons/49995

접근

구간합 문제이기 때문에 미리 구간합을 구해줍니다.O(Log N)

이러면 매번 계산하지 않아도 O(1)로 구간합을 구할 수 있습니다.

기본적인 알고리즘은 다음과 같습니다.

1. 첫번째 아들이 cookie[0,1,2,3 ... ]부터 1,2,3, .. N-1 개를 고름
   1-2. 두 번째 아들이 첫 번째 아들 바로 다음부터 1,2,3... 개를 고름

이렇게 하면 문제는 풀리지만 시간 초과가 납니다.

몇가지 조건만 추가하면 시간초과를 피할 수 있습니다.

1. 첫 번째 아들에게 줄 쿠키개수가 남은 모든 쿠키개수보다 크다면 검사하지 않습니다.
2. 두 아들에게 줄 쿠키의 개수가 전체구간 합을 2로 나눈 몫과 같다면 최대값이므로 더 이상 검사하지 않습니다.
3. 첫 번째 아들에게 줄 쿠키 개수가 현재 구한 최대 쿠키개수보다 작으면 검사하지 않습니다.

다음은 코드 전문입니다.

def solution(cookie):
    answer = 0

    section_sum = []
    N = len(cookie)
    for i in range(N):
        if i == 0 :
            section_sum.append(cookie[i])
        else:
            section_sum.append(cookie[i]+section_sum[i-1])


    maxi = 0
    isMaxFind = False

    for f in range(0,N):
        for l in range(1,N-f+1):
            if f == 0:
                f_sun = section_sum[f+l-1]
            else:
                f_sun = section_sum[f+l-1] - section_sum[f-1]

            s = f+l
            if f_sun > section_sum[-1] - section_sum[s-1]:
                break
            if f_sun < maxi:
                continue
            for l2 in range(1,N-s+1):
                s_sun = section_sum[s+l2-1] - section_sum[s-1]

                if f_sun == s_sun:
                    maxi = max(maxi,f_sun)
                    if maxi == section_sum[-1]//2:
                        isMaxFind = True
                    break
                    
                elif f_sun < s_sun:
                    break
            if isMaxFind:
                break
        if isMaxFind:
            break

    answer = maxi

    return answer