[백준] 1806 부분합

May 18, 2021 ( last updated : May 18, 2021 )
투 포인터 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 1806번 부분합

[백준] 1806번 부분합

백준 1806번

알고리즘 유형

풀이방법

low, high 두 수를 통해서 배열 상에서 더해주는 값들의 시작 점과 끝 지점을 표현해 준다. 하나씩 이동하면서 배열 내의 값들을 더하거나 빼면서 경우의 수를 카운트 해준다.

#include <algorithm>
#include <cstring>
#include <iostream>

#define MAX 100000 + 1
#define INF (1 << 31) - 1
using namespace std;

int N, S, ARR[MAX];

int main() {
  cin >> N >> S;
  memset(ARR, 0, sizeof(ARR));

  for (int i = 0; i < N; i++) {
    cin >> ARR[i];
  }

  int low = 0, high = 0;
  int sum = ARR[0];
  int result = INF;

  while (low <= high && high < N) {
    if (sum < S) {
      sum += ARR[++high];
    } else if (sum == S) {
      result = min(result, high - low + 1);
      sum += ARR[++high];
    } else if (sum > S) {
      result = min(result, high - low + 1);
      sum -= ARR[low++];
    }
  }

  if (result == INF) {
    cout << 0;
  } else {
    cout << result;
  }
  return 0;
}

Originally published May 18, 2021
Latest update May 18, 2021

Related posts :

{# #}