백준 1806번 부분합 문제 풀이

문제 설명

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

문제를 보고 든 생각

• 투 포인터를 사용하면 되겠다.
• 합이 클 수 있으니 unsigned long long 타입을 사용하자

풀이 간단 설명

1. lp, rp 모두 0에서 시작해서 합이 S 이상이 될 때 까지 rp를 증가시킨다.
2. 합이 S 미만이 될 때 까지 lp를 증가시킨다.
3. 1과 2를 하는 동안 간격의 최솟값을 저장한다.

코드

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ull;

ull N, S;
vector<ull> v;

void getInput(){
  cin >> N >> S;
  int n = N;
  while(n--){
    ull temp; cin >> temp;
    v.push_back(temp);
  }
}

void solve(){
  getInput();

  ull lp=0, rp=0;
  ull sumNum = 0;
  ull sumLen = 100000001;
  while(rp < N){
    sumNum += v[rp];
    if(sumNum >= S){
      ull diffLen = rp - lp + 1;
      if(sumLen > diffLen){
        sumLen = diffLen;
      }
      sumNum -= v[lp++];
      sumNum -= v[rp];

      continue;
    }

    ++rp;
  }
  
  if(sumLen == 100000001){
    cout << 0;
  } else{
    cout << sumLen;
  }
  return;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}