Algorithm

문제 바로가기
전체 소스코드 보기

문제

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

입력

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

출력

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

풀이

입력 받은 배열에 대하여 가장 앞쪽에 두개의 포인터를 두고 시작합니다.
해당 두개의 포인터는 합을 구할 구간을 나타냅니다.
해당 포인터 구간의 합이 주어진 s보다 작을 경우 hi를 증가 시켜 구간을 길게 만들어 줍니다.
이때 합이 s이상인 경우 현제 지정된 길이보다 작을 시 갱신 시켜주고 합에서 가장 낮은 값을 뺀후 포인터를 뒤로 옮겨줍니다.

위의 과정을 앞의 포인터가 뒤의 포인터보다 앞에 있을때 까지 그리고 뒤의 포인터가 배열을 넘어가지 않을 때 까지 반복후 길이를 출력해줍니다.

int findSubSum(vector<int>&nums, int s){
    int lo = 0;
	int hi = 0;
	int sum = nums[0];
	int len = nums.size() + 1;

    while (lo <= hi && hi < nums.size()) {
		if (sum < s) {
			sum += nums[++hi];
		}
		else {
			len = min(len, hi - lo + 1);
			sum -= nums[lo++];
		}
	}

    return len == nums.size() + 1 ? 0 : len;
}