[C++] BOJ 1806 - 부분합

BOJ 1806 - 부분합 (https://www.acmicpc.net/problem/1806)

01. 🔎 문제 탐색

N: 수열의 길이
S: 부분 수열의 합을 비교하기 위한 기준이 되는 수치
수열은 10,000 이하의 자연수로 이루어짐

 

* 부분 수열의 합이 S이상이 되는 것 중, 가장 짧은 것의 길이를 출력

01-1. 가능한 시간 복잡도

• 시간 제한 0.5초로 시간 복잡도 O(NlogN) 이하로 구현 가능

01-2. 알고리즘 선택

• 모든 부분 합을 살펴봐야 하므로, 투 포인터 알고리즘을 이용
  
  • 각 범위에 대해 처음부터 계속 더해줄 경우, 최악의 경우 시간 복잡도가 O(N^2) 이 될 수 있음
• 때문에, 슬라이딩 윈도우 를 이용하여 합하면, 시간 복잡도 O(N)이 보장

02. 📝 코드 설계하기

1. 수열의 길이 N과 비교 기준이 되는 수 S를 입력
2. 길이 N만큼의 수열을 입력
3. start와 end를 0으로 초기화
4. sum에 end를 계속 1씩 증가시키며, end번째에 있는 값을 계속해서 누적
5. sum이 S와 같거나 커졌을 때, 현재 저장된 결과와 sum을 비교하여 더 작은 값을 저장
6. sum이 S보다 커졌으므로, start를 1증가
7. end가 N에 도달할 때까지 4-6 과정을 반복

03. 🛠️ 시도별 수정

1회차

• 슬라이딩 윈도우 방식을 몰라서, 2중 for문 돌렸다가 시간초과..

---

04. 🗝️ 정답 코드

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

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

  ll N, S;
  vector<ll> seq;

  cin >> N >> S;

  for(int i = 0; i < N; i++){
    ll tmp;
    cin >> tmp;
    seq.push_back(tmp);
  }
  
  ll sum = 0;
  int result = INT_MAX;
  int start = 0;
  for(int end = 0; end < N; end++){
    sum += seq[end];

    while(S <= sum){
      result = min(result, end - start + 1);
      sum -= seq[start++];
    }
  }

  cout << (result == INT_MAX ? 0 : result) << "\n";

  return 0;
}