[Algorithm] programmers/kakao/2018winter/level4/쿠키 구입

문제 설명

과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N). 즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때, 조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를 return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

제한사항

cookie의 길이는 1 이상 2,000 이하입니다.
cookie의 각각의 원소는 1 이상 500 이하인 자연수입니다.

접근법

>> https://kyounju.tistory.com/6 의 c++코드를 참고하였습니다.

>> 우선 1부터 x 인덱스에 해당하는 요소까지의 accumulate[x]를 저장해둔다. 중복 계산을 피하기 위해서

>> 간단하게 말하면, 왼쪽 합과, 오른쪽 합을 비교해나가면 되는 것인데

>> 왼쪽 합은 c라는 변수로 표현하며, 우측 경계(m)이 고정된 상태에서 좌측 경계를 l이라는 변수로 조절한다.

>> 우측 합은 s라는 변수로 표현하며, s = accum[r] - c, where r in range(m+1, n+1)과 같이 표현할 수 있다.

>> 결국엔 잘 탐색해보라는 것인데, 여기서 "다" 탐색해볼 필요는 없다.

>> if answer >=s or s > c와 같은 조건문으로 필요없는 탐색을 중단할 수 있다. 

코드

def solution(cookie):
    answer = 0
    accum = [0 for _ in range(2001)]
    n = len(cookie)
    for i in range(n):
        sum[i+1] = sum[i] + cookie[i]
    for m in range(1, n):
        c = accum[m]
        for r in range(m+1, n+1):
            s = accum[r] - c
            if answer >= s or s > c :
                continue
            for l in range(m):
                if s == c-accum[l]:
                    answer = max(answer, s)
                    break
    return answer