1806번 부분합 문제를 풀어보았다.

1806 부분합

 

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

1806번: 부분합

 

이번 문제도 간단한 DP다.

단순히 부분 수열의 합이 S 이상 되는 것의 최소 길이를 출력하는 문제이다.

그래서 나는 DP[i]+=DP[i-1] 로 부분 수열들을 만들어놓고, DP[i]에서 DP[j]를 빼면서 수열의 길이별로 비교를 해보았다.

그 중에서 처음 S 이상의 합을 만족하는 가중치 t를 잡아놓았다면, 그 이하길이의 부분 수열은 합이 S를 넘을 수 없기 때문에 그냥 체크하지 않았다.

그리고 S 이상의 합을 만족하는 부분 수열이 체크될 때마다 길이를 비교하여 최소 길이를 구했다.

 

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n,s,r=0,i,j,t=0,k;
    long long int* DP;
    scanf("%d %d", &n, &s);
    DP=(long long int*)calloc(n+1,sizeof(long long int));
    for(i=1; i<=n; i++) {
        scanf("%lld", &DP[i]);
        DP[i]+=DP[i-1];
        if(DP[i]>=s && !r) {
            t=i;
            r=1;
        }
    }
    if(!t) {printf("0");return 0;}
    int MIN=t;
    for(i=t; i<=n; i++) {
        k=0;
        for(j=i-1; j>0; j--) {
            if(DP[i]-DP[j]>=s && !k) {
                r=0;
                if(MIN>i-j) MIN=i-j;
                k=1;
            }
            else if(k) j=-1;
        }
    }
    printf("%d", MIN);
}