백준 1806: 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

---

1. 문제 해석 

 

1.1. 투 포인터 알고리즘

포인터 2개(low, high) 를 이용해서 원하는 구간을 설정하면서 이동한다. 

- 정렬된 데이터 집합에서 합집합, 교집합 구하기 또는 특정값 이상의 부분합의 구간을 구하는 등의 문제에서 사용된다. 

 

5 1 3 5 10 7 4 9 2 8

1.2. 설계

숫자 배열 = num배열이라고 할 때
low = 0, high = 0, sum = num[0]

다음과 같이 값을 설정하고, 

sum 을 더해가되 sum이 S이상이라면 low를 증가시켜보면서 sum을 갱신하고, 

sum이 S보다 작다면 high를 증가시켜보면서 sum을 갱신한다. 

 

<주의점>

 sum 이 S 이상이라면 원하는 조건이므로 해당 구간의 길이를 구해서 최소라면 그 값을 저장한다.

값이 이동하면서 low > high 되거나 high가 전체 범위를 넘어갈 때 반복을 종료하도록 한다.

원하는 S이상의 부분합이 배열에 존재하지 않을 수도 있으므로, minlen 의 초기값이 변경되었는지 여부도 조사해서 맞게 값을 변경한다.(여기서는 0으로)

 

 

설계한 코드 

1. sum = num[0], minlen = MAX
low = 0, high = 0
2. while(low <= high && hugh < N)
	if(sum >= S)
    	sum <- sum + num[low]
      	low <- low + 1
        minlen <- min(minlen, high - low + 1)
    else
    	sum <- sum + num[high]
        high <- high + 1
        
3. if (minlen = MAX)
	minlen = 0
4. return minlen

 

 

2.  구현한 코드는 다음과 같다. 

#include <stdio.h>
#include <iostream>
#include <vector>

vector <int> nums;
#define MAX  2147483647


int N, S;
int min(int a, int b)
{
	return a < b ? a : b;
}

void input()
{
	int n;
	for (int i = 0; i < N; i++)
	{
		cin >> n;
		nums.push_back(n);
	}
}

int find_min()
{
	int low = 0, high = 0;
	int minlen = MAX;
	int sum;
	sum = nums[low];
	while (low <= high && high < N)
	{
		if (sum < S)
		{
			sum += nums[++high];
			
		}
		else
		{
			minlen = min(minlen, high - low + 1);
			sum -= nums[low++];
		}

	}
	if (minlen == MAX)
		minlen = 0;
	return minlen;

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> S;
	input();	
	cout << find_min() << "\n";
}