백준 1806 - 부분합

문제 설명

 

 

 

예제 입력 / 출력

 

 

=> 투 포인터 알고리즘의 개념을 알면 풀 수 있는 문제입니다. (저도 이 문제를 풀면서 처음으로 해당 알고리즘을 들었습니다.) 

 

=> start 점과 end 점의 위치를 변환해가며 S의 값을 넘으면 가장 적은 길이를 찾아내는 방법입니다. 

 

=> while문에서는 end가 0 인경우에 값을 부분합에 포함하지 않으므로, 이전에 값을 더해주는 과정이 필요합니다. 

 

=> while문을 통해 start 점이 end점을 앞서지 못하도록 하며, end점이 N(배열 원소의 개수)를 넘지 못하도록 합니다.

(배열의 끝점 = (원소의 갯수 -1) )

 

=> 부분합이 S를 넘지 못할 경우 end점을 뒤로 한 칸 미루며 다시 한번 계산합니다. 

 

=> 부분합이 S인 경우, 최소값을 구하고 다시 한번 end점을 뒤로 미룹니다. ( 이후 부분합이 S값을 넘는 경우에서 해당 값은 걸러집니다. )

 

=> 부분합이 S를 넘는 경우, start점의 값을 부분합에서 빼며 start점을 뒤로 미룹니다. (ex  start의 위치 : 0 →1 ) 

 

=> 해당 과정을 while문이 끝날때까지 반복합니다.  

 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <limits.h>


using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
   
    int arr[100001];
    int N, S;
    const int INF = INT_MAX;
    
    cin >> N >> S;
    
    for(int i=0; i<N; i++) cin >> arr[i];
    
    
    int start=0, end =0;
    int sum = arr[0];
    int answer = INF;
    while(start <= end && end < N )
    {
        if (sum < S) // 아직 부분합이 S를 만족하지 못하는 경우
        {
            sum += arr[++end];
        }
        else if ( sum == S)//원하는 값을 찾았을 경우
        {
            answer = min(answer, (end - start +1)); //최소값 찾기
            sum += arr[++end];
        }
        else //원하는 값보다 큰 경우
        {
            answer = min(answer, (end - start +1)); //최소값 찾기
            sum -= arr[start++];
        }
    }
    
    if (answer == INF) answer =0;
    cout <<answer<<'\n';
    
    return 0;
}

 

 

 

 

실행 화면