백준 1806 부분합 / C++

문제 : 1806

풀이 point

투 포인터를 통해 푼다. 시작과 끝이 있을 때 sum + arr[end]를 한다. 만약 S보다 크면 st를 한칸 땡긴다. 그렇지 않으면 end를 땡긴다. end가 N까지 다달았다면 st를 조정한다.

풀이 방법

이런 식으로 st와 end를 조절하며 최솟값을 갱신해나간다. 단 end가 N에 다달았을 때는 st만 조정해야한다.

코드

//백준 1806, 부분합

#include <iostream>

int arr[100'000];

int main (){

    int N, S;
    std::cin >> N >> S;
    for(int i{0}; i<N; ++i) std::cin >> arr[i];
    
    int st{0}; int end{0}; int sum{0}; int min = 100'001;
    while(st < N){
        if(sum >= S){
            sum -= arr[st];
            min = std::min(min, end-st);
            ++st;
        }
        else if(end == N){
            sum -= arr[st];
            ++st;
        }
        else{
            sum += arr[end];
            ++end;
        }
    }
    std::cout << (min == 100'001 ? 0 : min);
    return 0;
}

2025-02-07T02:25:22.582Z