[8] [Class 5] - 백준 1806 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

팀원 친구들이 레벨 6 풀고 있을때 나는 레벨 5에서 맞왜틀하고있어서 맘이 안좋았다

그치만 역시 꾸준한 노력이 답이기에.. 오늘도 존버.. 

 

연속된 수의 부분합 중에 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제

N이 10만이여서 복잡도가 O(NlogN) 이하로 나와야 된다고 생각했고

우선 구간 합을 다 구해놓고, 구간합은 크기에 대해 정렬된 상태이기 때문에

이분 탐색을 이용해서 적절한 값을 얻어내면 될 것이라 생각했다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> datas;

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  int N,S,d;

  cin >> N >> S;

  cin >> d;
  datas.push_back(d);

  for(int i = 1 ; i < N ; i++){
    cin >> d;
    datas.push_back(d);
    datas[i] += datas[i - 1]; // 이전값을 다 더함
  }

  int minVal = 100001;
  for(int i = 0 ; i < N ; i++){ // O(N)
    vector<int>::iterator it = lower_bound(datas.begin() + i, datas.end(), S + datas[i]); // O(logN)
    if(*it - datas[i] >= S){
      int len = it - (datas.begin() + i);
      if(minVal > len) minVal = len;
    }
  }

  if(minVal == 100001){
    if(datas[N-1]>=S){
      cout << N;
      return 0;
    }
    cout << 0;
  }
  else cout << minVal;

  return 0;
}

 

이게 그 결론.. 좀 더러운 코드가 몇개 있는데 

전체 구간의 합이 S인 경우가 안나와서 맨 밑의 if문에 조건을 하나 더 추가했다.