BOJ 1806 · 부분합

알고리즘 분류 : 투 포인터  

N 길이의 수열에서 연속된 수들의 부분합이 S 이상 되는 것 중, 가장 짧은 것의 길이를 구하는 문제다. 투 포인터 알고리즘을 응용하면 된다. 투 포인터에 대한 설명은 BOJ 2003번 '수들의 합 2' 문제를 참조.

---

C++ 소스코드

#include <cstdio>

int n, m, len, sum, left, right;
int a[100000];

void solve() {
    int ans = 1e9;
    while (true) {
        if (sum >= m) {
            if (ans > len) ans = len;
            sum -= a[left];
            left++;
            len--;
        } else {
            if (right == n) break;
            sum += a[right];
            right++;
            len++;
        }
    }
    printf("%d\n", ans == 1e9 ? 0 : ans);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    solve();
    return 0;
}

---

Python 3 소스코드

n, m = map(int, input().split())
a = list(map(int, input().split()))

def solve():
    left = right = k = s = 0
    ans = 1e9
    while True:
        if s >= m:
            ans = min(ans, k)
            s -= a[left]
            left += 1
            k -= 1
        else:
            if right == n:
                break
            s += a[right]
            right += 1
            k += 1
    print(ans if ans != 1e9 else 0)

solve()

---

참고

• 백준 온라인 저지 : BOJ 1806
• 수들의 합 2