[BOJ] 1806 : 부분합

문제 링크

1806번: 부분합 (acmicpc.net)

1806번: 부분합

풀이

부분수열의 합이 S이상 되는 부분수열중 가장 짧은 길이를 찾는 문제.

골드이상엔 브루트포스로 푸는 문제는 거의 없다고 보면 된다.

이것도 브루트포스로 풀면 당연히 시간초과.

임의의 인덱스 i 에서 i + a 까지의 부분합을 어떻게 빠르게 구할까

반복문으로 i부터 i+a까지 더한다? 효율이 떨어진다

Sum이라는 배열에 각 인덱스까지의 합을 저장한 다음 Sum[i+a] - Sum[i-1]을 하면 O(1)만에 찾을 수 있다.

그렇게 해서 부분수열의 길이를 기준으로 이분탐색을 한다.

길이가 1인 부분수열 즉 S보다 큰 값이 그냥 배열에 존재한다면 입력받을 때 판별해서 끝낸다.

그러므로 최소 길이인 2부터 최대길이 N 까지를 탐색 (Left = 2, Right = N)

길이가 mid인 부분합이 S이상인 부분수열이 존재하면 길이를 줄이기 위해 R = mid - 1.

존재하지 않으면 길이를 늘리기 위해 L = mid + 1. 이렇게 탐색하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef priority_queue <pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100000 + 5;
int N,S;
int ans = INF;
vector<int> V;
ll sum[MAX_N];
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> S;
    V.push_back(0);
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        if (S <= num) {
            cout << "1" << "\n";
            return 0;
        }
        V.push_back(num);
    }
    sum[0] = 0;
    for (int i = 1; i <= N; i++) {
        sum[i] = sum[i - 1] + V[i];
    }
    if (sum[N] < S) {
        cout << "0" << "\n";
        return 0;
    }
    int L = 2;
    int R = N;
    int ans = INT_MAX;
    while (L <= R) {
        int mid = (L + R) / 2;
        bool chk = false;
        for (int i = 0; i <= N - mid; i++) {
            if (sum[i + mid] - sum[i] >= S) {                
                chk = true;
                break;
            }
        }
        if (chk) {
            R = mid - 1; 
            ans = min(ans,mid);
        }
        else L = mid + 1;
    }
    cout << ans<< "\n";
    return 0;
}

이렇게 해주면 시간초과없이 통과