[백준] 1806 부분합

✔️ 문제 링크

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

1806번: 부분합

---

✔️ 문제 이해

1. 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 있다.

2. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구해야한다.

3. 범위 : N (10 ≤ N < 100,000),  S (0 < S ≤ 100,000,000)

---

✔️ 설계

1. 두 포인터를 사용한다. (S를 기준으로 구간합의 경우의 수를 생각한다.)

2. 구간합이 S이상이 될때마다, 구간 길이를 계산하고 최소값을 갱신한다. 

---

✔️ 문제 회고

1. 두 포인터의 개념을 알고 있어서, 비교적 빨리 풀 수 있었다.

2. 문제 조건을 잘못읽어서 시간 낭비를 했다. 'S 이상' 인데 'S와 같은' 으로 착각했다.

3. 구간합 구하기 문제는 두 포인터로 쉽게 해결할 수 있다.

 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, s;
int arr[100000];
int res = 0x7fffffff; //최소값을 구할 것이므로 int 범위 최대값으로 초기화한다. 

int main() {
	cin >> n >> s;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	//시작점을 가리키는 포인터, 끝점을 가리키는 포인터, 구간 합 
	int start = 0, end = 0, sum = 0;

	while (end <= n) {
		if (sum < s) { //구간합이 s보다 작으면 end를 증가
			sum += arr[end++];
		}
		else if (sum > s) {//구간합이 s보다 크면 start를 증가
			res = min(res, end - start); //구간 길이 최소값 갱신
			sum -= arr[start++];
		}
		else if (sum == s) {//구간합이랑 s랑 같으면 end를 증가
			res = min(res, end - start); //구간 길이 최소값 갱신
			sum += arr[end++];
		}
	}
	
	if (res == 0x7fffffff) //조건에 맞는 구간합이 없을 경우
		cout << 0;
	else
		cout << res;

	return 0;
}