01806번 부분합

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

Keywords: Programming Contest Challenging

전형적인 투 포인터 문제이다. 이렇게 주어진 모든 수가 자연수인 경우에 투 포인터 알고리즘은 모든 부분함 경우의 수를 빠짐없이 헤아릴 수 있음을 기억해두도록 하자.

아래는 솔루션이다.

#include <iostream>
#include <vector>

using namespace std;

int N;
int S;
int ARR[100'000];

int main(void) {
  // For faster IO.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  // Read inputs.
  cin >> N >> S;
  for (int i{0}; i < N; ++i) {
    cin >> ARR[i];
  }

  // Solve.
  int answer{N + 1};
  int sum{ARR[0]};
  int s{0}, e{0};
  while (e < N) {
    if (sum < S) {
      sum += ARR[++e];
    } else {
      answer = min(answer, e - s + 1);
      sum -= ARR[s++];
    }
  }

  // Print answers.
  cout << (answer == N + 1 ? 0 : answer) << '\n';

  return 0;
}