백준(C) 1806번 [부분합]

부분합 1806번

접근방법

부분합 문제는 N개의 10000 이하 자연수가 주어지고 이 수열에서 연속된 수의 합 중에 s이상이 되는것, 그중에서 길이가 짧은 것을 찾는것이다.

그렇게 되면 투포인터를 쓸수있다. 조건은 l 포인터 부터 r 포인터까지 더한게 s보다 크면 l을 늘려 줄이고 작으면 r을 늘려 크게 만들면된다. 탈출 조건은 r이 n을 넘으면 이다.

즉 r이 n이 넘을 때까지 조건문을 반복하며 s보다 같거나 크면 연속된 수의 크기를 저장 하고 다시 비교하고 작은거 저장하고... 반복하다보면 문제 해결이다.

 

투포인터 문제인걸 캐치하고 조건문만 잘 설정하면 쉬운 문제이다.

가장 주의할 점은 만약 못찾았을 경우이다. 이때는 초기 값을 아예 int 최대값 (INT_MAX)로 잡아 못찾아서 min_size(연속된 수의 길이)를 수정하지 못했을경우 0을 출력하게 만들면된다.

 

코드는 다음과 같다.

#include <stdio.h>
#include <math.h>
#include <limits.h>

int main(void)
{
    int n, s;
    scanf("%d %d", &n, &s);
    int num_s[100001];

    for (int a = 0; a < n; a++)
    {
        scanf("%d", &num_s[a]);
    }

    int l = 0, r = 0, min_size = INT_MAX, out = 0;

    while (r <= n)
    {
        if (out >= s)
        {
            if (r - l < min_size)
            {
                min_size = r - l;
            }
            out -= num_s[l++];
        }
        else
        {
            if (r == n)
                break;
            out += num_s[r++];
        }
    }

    if (min_size == INT_MAX)
        printf("0\n");
    else
        printf("%d\n", min_size);

    return 0;
}