[백준 1806] 알고리즘 105일차 : 부분합

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

1806번: 부분합

투포인터 C++

투포인터 첫문제

 

접근방법

시작점과 끝점을 이용해서 탐색의 시간복잡도를 줄이는 투포인터 문제이다.

대략적인 개념은 이해가 가는데 코드 구현 부분에서 헷갈리는 지점이 많았다.

 

1. 범위

결과적으로는 내가 포함시키고자 하는 범위가 항상

시작점 <= sum의 원소들 <= 끝점 이어야 한다.

따라서 길이 계산시에 E - S + 1 식을 사용해야하고 // 길이 계산을 먼저해야하며 // 끝점을 오른쪽으로 한칸 옮길때 그 수까지 더해줘야한다.

( 그래서 endpoint++ 가 아니라 ++endpoint 이어야 한다. )

처음에는 시작점 <= 원소들 < 끝점으로 생각하고 코드를 작성했다가 끝점이 N 이상일때 while문에 들어오지 못해서 오류가 발생했다.

 

2. sum의 초기값

sum의 초기값은 배열의 첫번째 원소여야 하는데

이 이유도 sum의 포함된 원소들은 항상 시작점 <= 원소들 <= 끝점 을 만족해야하기 때문이다.

시작점과 끝점이 0으로 초기화되는데 이 경우 sum은 0번~0번을 포함하고 있는 값이어야 하기 때문이다.

 

3. while 문 조건

while문 조건으로 끝점 < N(원소수) 외에도 시작점 <= 끝점을 넣어줘야한다.

시작점이 끝점보다 앞서가는 경우는 시작점 == 끝점 이고 sum > S 일때 즉, 시작점과 끝점이 같은 곳에 위치한 원소 하나가 S보다 크거나 같을때이다. 이 경우 길이가 나올 수 있는 최소값인 1인 경우이므로 반복문을 더 돌 필요가 없어 나오면 된다.

 

+) 그리고 sum == S 일때를 따로 처리하지 않아도 된다. sum이 S 이상일때 최소길이를 구하는 것이므로

크거나 같을때, 길이를 먼저 구한 후에 시작점을 앞으로 한칸 옮겨주면 된다.

그러면 sum == S 일때의 길이는 보존되기 때문에 문제없다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    //input
    int N, S;
    cin >> N >> S;
    
    int arr[N];
    for(int i = 0 ; i < N ; i++){
        cin >> arr[i];
    }
    
    //process
    int sum = arr[0];
    int len = N+1;
    int startPoint, endPoint;
    startPoint = endPoint = 0;
    while(startPoint <= endPoint && endPoint < N){
        if(sum >= S){
            len = min(len, endPoint - startPoint + 1);
            sum -= arr[startPoint++];
        }else{
            sum += arr[++endPoint];
        }
    }
    
    //output
    cout << (len > N ? 0 : len ) << endl;
    
    return 0;
}