[BOJ 1806] 부분합

문제 링크 : https://www.acmicpc.net/problem/1806

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

제한

시간 제한	메모리 제한
0.5sec (하단 참고)	128MB

---

풀이

이 문제는 $10\,000$ 이하의 자연수로 구성된 길이 $N$($10 \leq N < 100\,000$)인 수열에서, 연속된 부분합이 $S$($0 < S \leq 100\,000\,000$) 이상이 되는 구간 중 가장 짧은 길이를 찾는 문제이다. 시간 제한이 $0.5$초로 매우 촉박하기 때문에, 모든 구간을 탐색하는 $O(N^2)$ 방식으로는 해결할 수 없다. 따라서 선형 시간 복잡도를 가지는 투 포인터 알고리즘을 사용한다.

알고리즘의 동작 방식은 다음과 같다:

• 포인터 초기화: 구간의 시작을 가리키는 l과 끝을 가리키는 r을 모두 0으로 설정한다.
• 조건별 포인터 이동:
  • 합이 $S$ 이상인 경우: 현재 구간의 길이(r - l)를 확인하여 최솟값(result)을 갱신한다. 그 후, 더 짧은 구간이 있을 수 있으므로 왼쪽 포인터 l을 한 칸 전진시키고 합에서 arr[l]을 뺀다.
  • 합이 $S$ 미만인 경우: 합을 키우기 위해 오른쪽 포인터 r을 한 칸 전진시키고 합에 arr[r]을 더한다.
• 불가능한 경우 처리: 탐색이 끝난 후에도 최솟값이 초기값($100\,001$) 그대로라면, 조건을 만족하는 부분합이 존재하지 않는 것이므로 0을 출력한다.

이 방식은 각 포인터가 수열의 끝까지 한 번씩만 이동하므로 $O(N)$의 시간 복잡도로 문제를 해결할 수 있다. 수열의 원소가 최대 $10\,000$이고 $N$이 최대 $100\,000$이므로 부분합은 최대 $1\,000\,000\,000$까지 커질 수 있으나, 이는 int 자료형의 범위 내에 있으므로 안전하게 계산할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 투 포인터