[백준 / BOJ] C++ 1806 부분합

1806번: 부분합

 

문제

 

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

1806번: 부분합

 

 

풀이

부분합이 S 이상인 부분합 중 길이가 가장 작은 것의 길이를 구하는 문제다. 시간복잡도가 O(N^2)인 알고리즘으로 풀면 시간 초과를 받는다. 따라서 O(N)인 알고리즘으로 풀어야 한다. 그중 하나가 투 포인터를 사용해서 푸는 방법이다.

 

left와 right를 모두 0으로 두고 sum = v[0]으로 초기값을 설정한다. 합(sum)은 인덱스가 left부터 right까지 수열의 합이다. 수열의 각 수에 대해 현재까지의 합을 확인한다. 투 포인터를 사용했고 left부터 right까지의 합이므로 left가 right를 넘어가면 안 된다. 또한 right도 전체 수열의 크기인 n을 넘어가면 안 된다.

 

• 합이 S보다 작으면 right를 1 증가시키고 right 인덱스의 수를 합에 더한다.
• 합이 S와 같으면 수열의 크기가 답보다 작으면 갱신한다. 그리고 right를 1 증가시키고 right 인덱스의 수를 합에 더한다.
• 합이 S보다 크면 수열의 크기가 답보다 작으면 갱신한다. 그리고 left 인덱스의 수를 합에서 빼고 left를 1 증가시킨다.

위 방법대로 전체를 탐색하면 시간복잡도 O(N)으로 답을 구할 수 있다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, s;
  cin >> n >> s;
  vector<int> v(n, 0);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  int left = 0, right = 0, sum = v[0], ans = n + 1;
  while (left <= right && right < n)
    if (sum < s) {
      sum += v[++right];
    } else if (sum > s) {
      ans = min(ans, right - left + 1);
      sum -= v[left++];
    } else {
      ans = min(ans, right - left + 1);
      sum += v[++right];
    }
  cout << (ans == n + 1 ? 0 : ans);
  return 0;
}