[BOJ] 1806 - 부분합

https://www.acmicpc.net/problem/1806

BOJ - 부분합

문제 유형: 부분합, 투 포인터, 슬라이딩 윈도우

문제 난이도: Gold IV

시간 제한: 0.5초

메모리 제한: 128MB

 

문제

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

 

입력

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

 

출력

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

 

풀이

슬라이딩 윈도우를 이용하면 된다.

매번 right를 더해줄 때마다, left쪽에서 뺄 수 있는만큼 빼본다.

right를 한칸 밀면, left쪽에서는 sum이상인동안 최소길이를 업데이트하면서 left를 밀어본다.

 

최종적인 최소길이를 구한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, s;
  int arr[100000];
  cin >> n >> s;
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  int ans = INT_MAX;
  int l = 0;
  int sum = 0;
  for (int r = 0; r < n; ++r) {
    sum += arr[r];
    while (sum >= s && l <= r) {
      ans = min(ans, r - l + 1);
      sum -= arr[l];
      ++l;
    }
  }

  if (ans == INT_MAX)
    ans = 0;
  cout << ans << "\n";

  return 0;
}