1806번 : 부분합 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (13분)

아이디어

단순 중첩 반복문으로 진행을 하면 누적합 배열을 만들고

인덱스를 i, j(j <= i) 로 만들고 i-j의 길이만큼을 다 비교해주면

구현은 가능하나 최악의 경우 O(N*N) 으로 시간초과가 난다.

그렇기에 내가 생각한 방법은 누적합 배열을 구하고 순회를 하며 

sum[i] - sum[j]를 진행하는데 ( i >= j) i는 1~N까지 순회해주고 

j는 이분탐색을 통해서 가장 짧은 길이의 연속합을 구할 수 있는 인덱스를 구하게 된다. 

그럼 NlogN으로 시간초과에서 안심

그리고 len값은 해당 구간합이 S이상일때 계속 최소값으로 최신화를 해주었음.

풀이 코드

#include<iostream>
#include<vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int    N, S;
    cin >> N >> S;
    vector<int> arr(N + 1, 0);
    vector<long long int> sum(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    for (int j = 1; j <= N; j++) {
        sum[j] = sum[j - 1] + arr[j];
    }
    int INF_MAX = 0x7f7f7f7f;
    int len = INF_MAX;
    // 누적합 순회
    for (int i = 1; i <= N; i++) {
        int left = 0;
        int right = i;
        int mid = (left + right) / 2;
        // 빼줄값 이분탐색으로 찾기 
        while (left<=right) {
            int mid = (left + right) / 2;
            long long int summary = sum[i] - sum[mid];
            // 이상이더라도 계속 진행 -> 최소한의 길이를 구해야 하기에
            if (summary >= S) {
                len = min(len, i - mid);
                left = mid + 1;
            }
            //만약 합이 적다면 인덱스더 줄이기 -> 합이 커짐
            else if (summary < S) {
                right = mid - 1;
            }
        }
    }
    int answer = len == INF_MAX ? 0 : len;
    cout << answer;
    return 0;
}