[C/C++] 백준 #1806 부분합(두 포인터)

이번 문제는 두개의 포인터를 운용해서 푸는 방법입니다.  부분합인데 연속된 수열의 부분합이란 점이 문제를 푸는데 있어서 중요합니다.

 

예를 들어서 1 3 2 4 7 8 3 6 이란 수열이 있다고 하죠.  여기서 부분합이 20이상일 때 최소의 N을 구하도록 하면요.

 

처음부터 누적하여 부분합이 20이 넘는 곳을 찾습니다.

1	3	2	4	7	8	3	6
1	4	6	10	17	25

그러면 8에서 멈추게 되는데, 이 때부터는 앞에서부터 하나씩 제거해서 20 미만이 되는 시점을 찾습니다.

그러면 4의 숫자에서 멈추게 됩니다.  여기서 다시 오른쪽 숫자를 포함하면서 20 이상이 되는 지점을 찾습니다.  왜 앞에서부터 다시 안 찾는가하면, 이미 바로 앞의 숫자를 포함하고 뒤의 숫자를 포함하는 것은 의미가 없기 때문입니다.  최소의 N을 찾는 것이기 때문이죠.

1	3	2	4	7	8	3	6
			4	11	19	22

 

이렇게 하면 3이란 숫자에서 또 멈추고, 다시 앞의 작업을 반복하면 최소의 N을 구할 수가 있습니다.

1	3	2	4	7	8	3	6
				7	15	18	24

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------
//    baekjoon #1806 - Partial Sum
//        - by Aubrey Choi
//        - created at 2019-07-01
//------------------------------------------------
#include <stdio.h>
#define    INF    1000000

int main()
{
    int n, s, sum = 0, sp = 0, min = INF;
    static int v[100000];
    scanf("%d%d", &n, &s);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &v[i]);
        sum += v[i];
        while(sum >= s && sp <= i)
        {
            if(min > i-sp+1) min = i-sp+1;
            sum -= v[sp++];
        }
    }
    printf("%d\n", min>=INF?0:min);
}