백준1806 부분합 - C++

1<= x <= 10000 으로 이루어진 길이 N짜리 수열이다.

연속된 수들의 부분합 중 합이 S 이상인 것만 고른 후

가장 짧은 부분합 수열의 길이를 구해보자.

단 N은 100,000 개, S는 1억까지 가능하다.

 

먼저 S가 1억 이하이므로 Integer 를 사용하면 될 것 같다.

부분합은 차례대로 구해보자.

N = 10 일 경우 부분합의 경우의 수는 다음과 같다.

부분수열의 크기    수열        개수

1 : 1,2,3,4,5,6,7,8,9,10    : 10

2 : 12,23,34,45,56,67,78,89,910 : 9

3 : 123,234,345,456,567,678,789,8910 : 8

4 : 1234,2345,3456,4567,5678,6789,78910 : 7 

5 : 12345,23456,34567,45678,56789,678910 : 6

6 : 123456,234567,345678,456789,5678910 : 5 

7 : 1234567,2345678,3456789,45678910 : 4 

8 : 12345678,23456789,345678910 : 3

9 : 123456789,2345678910 : 2 

10 : 12345678910 : 1

 

즉 개수는 Sigma(n=1 ~ 10) (n) 이 되고 

이는 중학교에서 배우듯이 n (n+1) / 2 개이다.

즉 부분수열의 개수만 5000 * 10001 개이므로 

0.5 초 안에 전부 탐색하는 것은 힘들다.

 

고로 집중해야 할 것은 가장 짧은 길이의 부분 수열을 구하는 것이다.

 

이분 탐색으로 Nlog(N) 으로 풀 수도 있겠지만

N 으로 풀어보자.

 

이 문제에서 부분 수열은 항상 연속적으로 붙어있기 때문에

슬라이딩 윈도우를 사용하여 볼 수 있다.

 

만약 a = [5, 1, 6, 23, 4 ,3 ,10, 7] 이라는 수열이 있고

S=10 이라고 해보자.

그럼 가장 왼쪽에 있는 index 를 start,

가장 오른쪽에 있는 index를 end 라고 가정하고

start=0, end=0에서 부터 출발해보자.

 

그럼 부분수열의 합 sum = a[start] + a[start+1] ...+ a[end-1] + a[end] 가 될 것이다.

 

시작 sum = a[start] 로 두므로 위의 경우는 sum = 5가 된다.

그 후 sum 이 S 보다 큰지 작은지를 확인하면서

 

1. sum 이 S 보다 같거나 큰 경우 현재 길이가 최소인지 확인하고 저장한 후 

sum 이 줄어들어야 더 짧은 길이를 가질 수 있으므로 start = start+1 하여 

start 를 한 칸 우측으로 옮긴다.

 

2. sum 이 S 보다 작은 경우 부분 수열이 더 늘어나야 하므로

end = end+1 하여 end를 우측으로 한 칸 옮긴다.

만약 start>end 라면 즉시 종료한다.

중간에 start > end 라면 길이가 1인 수열이 제일 짧은 것이므로

종료해도 이상이 없다.

 

 

len 은 N이 최대 10만이 나올 수 있으므로 

초기값을 10만 + 1으로 잡고, 만약 더 짧은 것이 발견되지 않았다면

만들기 불가능한 경우이므로 0을 출력한다.

 

위의 풀이 방법으로 반드시 해를 찾을 수 있을까?

 

s,e 를 index로 보고 start, end 를 가장 짧은 수열의 인덱스로 보자.

슬라이딩 윈도우의 상황을 여섯 가지로 볼 수 있을 것 같다.

 

1. s, e 가 모두 start 보다 작을 경우

2. s 가 start 보다 작고 e가 start 보다 같거나 크고  end 보다 작은 경우

3. s 가 start 보다 작고 e가 end 보다 같거나 큰 경우

4. s 가 start 보다 같거나 크고 e 가 end 보다 작은 경우

5. s 가 start 보다 같거나 크고 e 가 end 보다 같거나 큰 경우

6. s, e 가 모두 end 보다 큰 경우

 

1.의 경우 가장 짧은 수열과 같은 길이를 찾을 수도 있겠지만 못 찾아도 상관없다.

왜냐하면 while(s<=e ) 의 조건이기 때문에 길이가 1이 아닌 이상 

2번의 상황으로 항상 넘어오기 때문이다.

 

2.의 경우 가장 짧은 수열의 길이가 정해져 있기 때문에 

이 상황에서 발견하는 가장 짧은 수열은, 우리가 기대하는 가장 짧은 수열의 길이와

같거나 크다. 

S 보다 작은 경우 e 가 늘어나 3의 상황으로 가거나

S 보다 큰 경우 s 가 늘어나 4의 상황으로 간다.

 

3. 의 경우 가장 짧은 수열을 포함하고 있기 때문에 e 는 end와 같은 지점에서 멈추고

s 가 start 와 같아질 때까지 sum >= S 를 만족하게 된다.

즉 s = start, e = end 가 되는 경우를 반드시 찾을 수 있다.

 

4. 의 경우 가장 짧은 수열보다 작으므로 sum < S 이다. 5번의 상황으로 간다.

 

5. 6. 은 의미가 없다. 왜냐하면 가장 작은 수열을 반드시 찾을 수 있다는 것을 

이미 알기 때문이다.

 

멋들어지게 수학으로 표현하면 좋겠지만

나는 상황이 더 잘 맞는 것 같다....

 

#include <cstdio>
#include <algorithm>

using namespace std;

int arr[100001];

int main()
{
	int N, S;
    scanf("%d %d", &N,&S);
	for (int i = 0; i < N; i++)  // 수열 입력
	{
        scanf("%d", &arr[i]);
	}

	int start = 0, end = 0, len = 1e6 + 1;
	int sum = arr[start];
	while (start <=end && end < N)
	{
		if (sum >= S)
		{
			len = min(len, (end - start + 1));
			sum -= arr[start++];

		}
		else
			sum += arr[++end];
	}
	if (len == 1e6 + 1)
        printf("0\n");
	else
        printf("%d\n", len);
    
	return 0;
}