[백준 BOJ] 1806 부분합 C++

 

문제

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

 

풀이

•  입력
  • 수열의 길이 N
  • 부분합 S
  • 수열
• 출력: 부분합의 최소 길이
• 알고리즘: 투포인터
  • 연속된 수들 중 주어진 부분합을 찾는 문제
  • 두 개의 점의 위치를 기록하며 처리하여 리스트에 순차적으로 접근하는 투포인터 사용

 

---

 

코드

#include <iostream>
#include <algorithm>
#define MAX 100010
using namespace std;

int N, S;

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

    cin >> N >> S;
    int arr[N];

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

    int s=0, e=0, sum=0, result=MAX;
    while (s <= e){
        if (sum >= S){
            result = min(result, e-s);
            sum -= arr[s++];
        } else if (e == N) break;
        else sum += arr[e++];
    }

    if (result==MAX) cout << 0 << '\n';
    else cout << result << '\n';

    return 0;
}