BOJ 1806 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

처음 보고 생각난 Naive한 방법은 모든 경우의 수를 계산해보는 방법이었다.

합 배열을 만드는데 O(N), 시작점-끝점 경우의 수가 N^2/2 이므로, 해당 방법은 O(N^2 + N) 으로 시간내에 풀이가 불가능했다.

 

문제 조건을 잘 보니 "수열의 값은 자연수"임을 확인할 수 있었다.

그렇다면 arr [ i : j ] 의 합을 구한 상태에서 arr [ j ]  을 더한다면 항상 arr [ i : j ] 보다 클 것이고, arr [ i ] 을 뺀다면 항상 arr [ i : j ] 보다 작겠다는 생각이 들었다.

이를 기반으로 이것이 주어진 합 S 이상이라면 i 를 늘려가면서 arr [ i : j ]의 합이 여전히 S보다 큰지 아닌지 확인하고, S 이하라면 j 를 늘려가면서 arr [ i : j ]의 합이 S보다 커졌는지 아닌지 확인하면서 최소길이를 갱신하면 되겠다고 생각하게 되었다.

이를 기반으로 코드를 작성하였다.

#include <cstdio>

int n;
unsigned long long arr[100000], s;

int main(){
    scanf("%d%llu",&n,&s);
    for(int i=0;i<n;i++){
        scanf("%llu", arr+i);
    }
    int i=0, j=0, answer = n+1;
    unsigned long long sum = arr[0];
    while(i<n){
        //printf("%d %d\n",i,j);
        if(sum < s){
            if(j+1 < n){
                ++j;
                sum += arr[j];
            }
            else{
                break;
            }
        }
        else{
            answer = answer < (j-i+1) ? answer : (j-i+1);
            sum -= arr[i];
            ++i;
        }
    }
    if(answer <= n)
        printf("%d\n",answer);
    else
        printf("0\n");

    return 0;
}