쿠키 구입

문제 보기 · Level 4 · Summer/Winter Coding(~2018) · 정답률 35% · 푼 사람 2,545명 (2026-09-30 기준)¹

문제

바구니 N개가 한 줄로 있고, 바구니마다 과자 수가 있다. 첫째 아들에게는 l ~ m번, 둘째 아들에게는 m + 1 ~ r번 바구니를 준다. 두 아들이 받는 과자 수가 같아야 한다. 이렇게 살 때 한 아들이 받는 과자 수의 최댓값을 돌려준다. 방법이 없으면 0이다.

바구니 1 ~ 2,000개
바구니의 과자 수 1 ~ 500

풀이

막히면 한 단계씩 펼친다.

필요한 개념

투 포인터와 슬라이딩 윈도: 두 아들 사이의 경계 m을 정하면, 왼쪽 끝은 왼쪽으로만, 오른쪽 끝은 오른쪽으로만 넓힌다. 과자 수가 모두 양수라 넓힐수록 합이 커지기만 한다.

1단계 · 작은 예로 손으로 풀기

[1, 1, 2, 3]에서 경계를 셋째와 넷째 바구니 사이에 둔다. 첫째는 셋째 바구니(2), 둘째는 넷째 바구니(3)에서 시작한다.

2 < 3이라 첫째 쪽을 왼쪽으로 넓힌다: 1 + 2 = 3. 3 = 3, 같다! 후보 3.
더 넓혀 본다: 1 + 1 + 2 = 4 > 3. 둘째 쪽을 넓히려 해도 오른쪽 끝이다. 멈춘다.

이 경계에서 가장 큰 값은 3이다. 작은 쪽을 넓혀 가며 두 합을 맞춰 보는 것이 핵심이다.

2단계 · 가장 단순한 방법과 그 속도

l, m, r을 모두 고르면 \(O(N^3)\), N = 2,000이면 80억 번이다. 누적 합으로 구간 합을 \(O(1)\)에 구해도 세 겹 반복은 그대로다.

3단계 · 핵심 아이디어

경계 m을 고정: 첫째의 합 ls는 l을 왼쪽으로 옮길수록, 둘째의 합 rs는 r을 오른쪽으로 옮길수록 커진다(과자 수가 모두 양수라서).
작은 쪽을 넓힌다: ls < rs면 ls를 키워야 같아질 수 있으니 l을 옮긴다. ls > rs면 r을 옮긴다. 같으면 답 후보로 적고, 다음 같은 값을 찾으려면 어느 쪽이든 넓혀야 하니 l을 옮긴다.
끝에 닿으면 멈춤: 넓혀야 할 쪽이 이미 끝이면, 그 경계에서는 더 같아질 수 없다.
두 끝이 각각 한 방향으로만 움직이니 경계 하나에 \(O(N)\), 경계 N − 1개에 \(O(N^2)\)이다.

4단계 · 코드 흐름

경계 m = 0 ~ N − 2마다: l = m, r = m + 1, ls = cookie[l], rs = cookie[r].
되풀이: ls == rs면 best를 갱신한다. ls ≤ rs면 l을 하나 왼쪽으로(끝이면 멈춤), 아니면 r을 하나 오른쪽으로(끝이면 멈춤).
best를 돌려준다.

5단계 · 파이썬 코드

def solution(cookie):
    n, best = len(cookie), 0
    for m in range(n - 1):                    # 첫째는 m에서 끝나고, 둘째는 m+1에서 시작
        l, r = m, m + 1
        ls, rs = cookie[l], cookie[r]
        while True:
            if ls == rs and ls > best:
                best = ls
            if ls <= rs:                       # 왼쪽이 작거나 같으면 왼쪽을 넓힌다
                if l == 0:
                    break
                l -= 1
                ls += cookie[l]
            else:                              # 오른쪽이 작으면 오른쪽을 넓힌다
                if r == n - 1:
                    break
                r += 1
                rs += cookie[r]
    return best

while True:와 break: 조건을 반복문 안에서 따져 멈춘다. 멈추는 곳이 두 군데라 이렇게 쓰는 편이 읽기 쉽다.
같을 때 왼쪽을 넓히다 왼쪽 끝이면 멈춘다. 이때 오른쪽을 넓히면 rs만 커져 다시 같아질 수 없기 때문이다.

6단계 · 실행 추적

[1, 1, 2, 3], 번호는 0부터

경계 m	(l, r)	ls	rs	한 일
1	(1, 2)	1	2	왼쪽 넓히기
1	(0, 2)	2	2	같다, 후보 2. 왼쪽 끝이라 멈춤
2	(2, 3)	2	3	왼쪽 넓히기
2	(1, 3)	3	3	같다, 후보 3. 왼쪽 넓히기
2	(0, 3)	4	3	오른쪽 끝이라 멈춤

경계 0에서는 1 = 1이 후보다. 모든 경계를 보면 답은 3이다.

7단계 · 복잡도와 흔한 실수

\(O(N^2)\), N = 2,000이면 약 400만 번이다. 재 보니 0.1초가 안 걸렸다.

경계를 정하지 않고 l, m, r을 모두 돌려 시간 초과가 난다.
같을 때 멈춰 버려, 더 큰 같은 값을 놓친다. 같아도 계속 넓혀 봐야 한다.
과자 수가 양수라는 조건을 쓰지 않고 이 방법을 다른 문제에 옮긴다. 음수가 있으면 넓혀도 합이 줄 수 있어 틀린다.

검증: 문제의 예시 2개를 통과했고, 6단계의 두 경계를 코드로 따라가 확인했다. 무작위 입력 3,000개에서 “누적 합으로 l, m, r을 모두 보는” 풀이와 결과가 같았다. 바구니 2,000개(값이 모두 같아 끝까지 넓히는 경우 포함)의 시간도 쟀다 — 18_pg49995_p1.py

프로그래머스 스쿨, “쿠키 구입” (https://school.programmers.co.kr/learn/courses/30/lessons/49995), 2026-09-30 조회. ↩