백준[boj 1806번: 부분합]

 

https://www.acmicpc.net/problem/1806

 

1806번: 부분합

 

문제 설명

수열의 크기 N과 최소합 S를 입력 받아 연속된 길이의 수열의 합중 길이악 제일 짧은 것을 출력하면 된다.

STEP 1

문제의 예시와 함께 따라가면, 5,1,3,5까지는 수의 합이 15 미만 이므로 , 수열의 길이를 계속 늘려야한다.

STEP 2

이후 10을 입력받은 시점에서,  최소인 동시에 S보다 크거나 같을 때까지 앞부분의 수열을 잘라내면서 최소 길이값을 갱신한다.

STEP 3

만약 잘라낸 길이가 S보다 다시 짧아지면,  다시 S 보다 크거나 같을때까지 뒷부분의 수열을 한칸씩 늘린다.

STEP 4

STEP 2-3을 반복하다가, 앞부분을 갱신할수 없어 뒷부분의 수열을 마지막으로 늘리는 순간 수열의 길이가 N+1이되면서 break가 걸린다.

 

 

 

정답 코드 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 100000;
int N, S;
int arr[MAX];
int sum[MAX];
int main() {
	
	cin >> N >> S;
	for (int i = 0;i<N; i++) {
		cin >> arr[i];	
	}
	int low = 0;
	int high = 0;
	int sumNum = 0;
	int len = 2e9;
	while (low <= high) {
	
		if (sumNum >= S) {
			//if(sumNum ==S)
				len = min(len, high - low);
			//cout << "sumNum" << sumNum << "arr[low]" << arr[low] << "\n";
			sumNum -= arr[low++];
			//cout << "sumNum" << sumNum << "arr[low]" << arr[low] << "\n";
		}
		else if (high == N ) break;
		else {
			sumNum += arr[high++];
		}
	
	}

	if (len == 2e9) {
		cout << 0;
		return 0;
	}

	else cout << len;

	return 0;
}

 

 

 

오답 사유

문제를 잘 읽자. 문자열 길이가 S와 같을 때가 아니라 S이상 일때 였다