문제 소개
정수로 이루어진 배열 nums가 주어졌을 때, 이 배열을 "좋은(good)" 방식으로 분할하는 서로 다른 경우의 수를 구하는 프로그램을 만들어 보겠습니다. 답이 매우 커질 수 있으므로 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다.
여기서 "좋은 분할"이란 다음 조건들을 동시에 만족하는 분할을 의미합니다.
- 배열을 왼쪽에서 오른쪽 순서대로 비어 있지 않은 세 개의 연속된(contiguous) 부분 배열로 나눈다.
- 왼쪽 부분의 원소 합 ≤ 가운데 부분의 원소 합
- 가운데 부분의 원소 합 ≤ 오른쪽 부분의 원소 합
예시
입력이 nums = [2,3,3,3,7,1]일 때 출력은 3입니다. 가능한 분할 방식은 다음 세 가지입니다.
- [2], [3], [3,3,7,1]
- [2], [3,3], [3,7,1]
- [2,3], [3,3], [7,1]
풀이 접근: 누적 합 + 두 포인터
모든 분할 지점을 완전 탐색하면 O(n²) 이상의 시간이 걸릴 수 있습니다. 하지만 누적 합(prefix sum) 배열과 두 포인터(two pointers) 기법을 함께 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 배열의 원소가 음수가 아니라면 누적 합은 항상 단조 증가하므로, 경계를 가리키는 두 포인터 r과 rr는 한 번 오른쪽으로 이동한 뒤 되돌아올 필요가 없기 때문입니다.
알고리즘의 전체 흐름은 다음과 같습니다.
- n := nums의 길이
- m := 10^9 + 7
- ss := 크기가 (n+1)인 배열을 만들고 0으로 초기화(누적 합 저장용)
- nums의 각 인덱스 i와 값 val에 대해 → ss[i] := ss[i-1] + val
- r := 0, rr := 0, ans := 0으로 초기화
- l을 1부터 n-2까지 반복:
- r := max(r, l+1)
- r < n-1이고 ss[r] − ss[l] < ss[l]인 동안 r을 1씩 증가
- rr := max(rr, r)
- rr < n-1이고 ss[n] − ss[rr+1] ≥ ss[rr+1] − ss[l]인 동안 rr을 1씩 증가
- ss[l] > ss[r] − ss[l]이면 반복문 종료(break)
- ss[r] − ss[l] > ss[n] − ss[r]이면 다음 반복으로 건너뜀(continue)
- ans := (ans + rr − r + 1) mod m
- ans 반환
여기서 포인터 r은 "가운데 합이 왼쪽 합보다 작아지지 않는" 첫 번째 위치를 찾고, rr은 "오른쪽 합이 가운데 합보다 작아지지 않는" 마지막 위치를 찾습니다. 따라서 l이 고정된 상태에서 유효한 가운데 경계의 개수는 rr − r + 1이 됩니다.
파이썬 구현 예제
아래 코드를 통해 실제 구현 과정을 확인해 보겠습니다.
def solve(nums):
n, m = len(nums), 10**9+7
ss = [0] * (1+n)
for i, val in enumerate(nums, 1):
ss[i] = ss[i-1] + val
r = rr = ans = 0
for l in range(1, n-1):
r = max(r, l+1)
while r < n-1 and ss[r]-ss[l] < ss[l]:
r += 1
rr = max(rr, r)
while rr < n-1 and ss[n]-ss[rr+1] >= ss[rr+1]-ss[l]:
rr += 1
if ss[l] > ss[r]-ss[l]:
break
if ss[r]-ss[l] > ss[n]-ss[r]:
continue
ans = (ans+rr-r+1) % m
return ans
nums = [2,3,3,3,7,1]
print(solve(nums))입력 및 출력 확인
입력
[1,7,3,6,5]
출력
3
배열 [1,7,3,6,5]의 경우 총 세 가지 방법으로 "좋은 분할"을 만들 수 있으며, 프로그램이 올바르게 3을 출력하는 것을 확인할 수 있습니다.