백준 1806 부분합

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

1806번: 부분합

 

 

EXPLANATION

 

수열에서 연속된 수의 부분합이 S보다 크거나 같은 것 중에 최소의 길이를 가지는 걸 찾는다.

수열에서 연속된 수의 부분합을 확인하는 것이므로 두 포인터로 수열의 처음 수부터 시작해서 뒤로가며 확인한다.

부분합이 S보다 크거나 같으면 그것보다 짧은 길이의 부분합이 S보다 크거나 같은 지를 확인해야 현재까지 구한 최소길이보다 더 짧은 길이의 그러한 부분합이 존재하는 지 확인할 수 있다.

일단 최소의 길이가 나오면 수열 뒤에 또 다른 경우에 최소의 길이가 존재하든 말든 상관없다.

어차피 둘다 최소의 길이고 부분합을 이루는 수가 무엇인지 상관 없으니까.

따라서 가장 최소의 길이가 될 수 있는 1개의 부분합이 나온 이후 수열을 끝까지 돌지 않고 종료해도 된다.

그러나 수열을 확인하면서 1개의 부분합이 가능한 경우가 나오지 않으면 수열이 끝날 때 까지 1개의 부분합이 가능한지 확인해봐야 한다. 따라서, 이 경우 부분합의 마지막 수가 수열의 마지막 수일 때까지 확인하고 그 이후에 종료 된다.

 

문제 조건에 맞는 부분합을 찾으면, 그 부분합에서 더 적은 길이로도 S보다 크거나 같은 지 확인해야 하려면 그 부분합을 이루는 연속된 수 중 가장 앞에 있거나 뒤에 있는 거를 빼고 확인해야 한다. 수열의 처음부터 시작해서 마지막으로 가는 순서로 확인하고 있으니 부분합을 이루는 연속된 수 중 가장 앞에 있는 수를 뺀다.

sum -= arr[start++] (현재 부분합이 가지고 있는 수를 부분합에서 뺌)

마찬가지로,  부분합이 S보다 작으면 연속된 수를 하나 더하기 위해 부분합을 이루는 수의 마지막 수보다 index가 하나 더 큰 원소를 부분합에 더 한다.

sum += arr[++end] (현재 부분합이 가지고 있지 않는 수를 부분합에 더함)

 

물론, 문제 조건에 맞는 부분합을 찾았을 때, 부분합의 최소 길이를 비교해서 답을 갱신.

 

 

 

CODE

#include <iostream>
#include <vector>
#include <algorithm>
int INF = 100000 + 1;
using namespace std;

int main() {
    int N, S;
    cin >> N >> S;
    vector<int> arr(N);
    for (int i = 0; i < N; i++) cin >> arr[i];

    int start = 0, end = 0, sum = arr[0];    //수열의 가장 첫번째 부터 탐색 시작.
    int minLen = INF;
    while (start <= end && end < N){    //최소길이가 1인 문제 조건에 맞는 부분합이 나왔거나, 부분합의 마지막 수가 수열의 마지막 수의 index를 넘어서면 종료.
        if (sum >= S) {    // 현재 포인터의 부분합이 S보다 크거나 같으면,
            minLen = min(minLen, end - start + 1);   // 부분합의 최소 길이 비교 후 갱신.
            sum -= arr[start++];    //부분합에서 부분합이 가지고 있는 가장 앞에 수를 뺌.
        }
        else    //현재 포인터의 부분합이 S보다 작으면,
            sum += arr[++end];    //부분합에 부분합이 가지고 있는 가장 마지막 수 다음 index의 수를 더함.
    }

    if (minLen == INF) cout << 0 << "\n";    //수열을 다 돌 동안 문제 조건에 맞는 부분합을 찾지 못했으면 0출력.
    else cout << minLen << "\n";
}

 

while(A && B)는 A이고 B일 때 while문 실행. 즉, !A 혹은 !B이면 while문 종료.

 

 

 

while문 안의 sum += arr[++end]에서 out of bounds 에러가 발생하지 않는 이유가 벡터는 범위를 벗어나면 랜덤값을 자동으로 할당해주는 거 같다. 단, vector가 텅텅비지 않은 경우에만.

 

부가 설명:

vector에 할당된 메모리를 벗어난다 하더라도

다른 변수, 포인터, 클래스 객체 etc.에게 할당된 곳이 아니면 접근해도 에러는 잘 안 납니다.

소스코드상에서 뭔가를 선언한다는 건

최소한 이만큼은 자유롭게 접근&사용할 수 있게 보장해 달라고 컴파일러에게 요청하는 것이고

여길 벗어나더라도 아무도 안 쓰고 있는 공터라면

운영체제 입장에서 굳이 에러를 내지 않고 내버려두는 걸 선택할 수도 있죠.

(항상 그렇다는 건 아닙니다.)

아래 예시를 돌려보시면 정확한 값은 환경마다 심지어 매번 다를 수 있으나

일반적으로 선언한 크기인 100을 한참 넘어가서야 segfault가 날 겁니다.

하나쯤 넘어가는 건 거의 100% 확률로 문제가 없겠죠.

그럼 왜 우리가 평소 코딩할 때는 그렇게 인덱스 하나 차이로 에러가 자주 날까요?

저 예시처럼 함수 안에 vector 하나만 달랑 있는 게 아니라

수~수십 개의 변수들과 객체들이 선언돼 있으면

메모리 효율이나 여러 가지 이유로

이들의 메모리 주소를 인접하게 배정하는 경우가 많기 때문입니다.

int main() {
    vector<int> vec(100);
    for (int i = 0; i < 1000000; i++)
        cout << i << ' ' << vec[i] << endl;
    // (...생략)
    // 15441 0
    // 15442 0
    // 15443 0
    // Segmentation fault
}