백준1806번(부분합)[C/C++]

🔗링크

1. 문제 풀이

카카오테크 캠퍼스 2차 코테에서 비슷하게 나왔던 유형인 투 포인트 문제이다.

간단한 그림으로 설명한다면

---

주어진 수열에 대해 포인터 두개를 준비한다.

---

그 후 누적합이 S보다 크거나 같아질 때까지
머리쪽 포인터를 순차적으로 전진시킨다.

---

이후 누적합이 S보다 크거나 같아졌다면 이제 조건을 만족하는 최소 길이를 구하기 위해
최소 누적합을 유지하며 꼬리쪽 포인터를 전진시킨다.

이동을 완료 후 기존 최솟값과 비교 및 갱신을 한다.

2. 코드

#include<stdio.h>

int arr[100001], min = 100001, S, N;

int main() {
	scanf("%d %d", &N, &S);
	int sum = 0;
	for (int i = 0,j = 0; i < N; i++) {
		scanf("%d",&arr[i]);
		sum += arr[i];
		if (sum >= S) {
			while (j < i) {
				if (sum - arr[j] < S)break;
				else sum -= arr[j++];
			}
			if (min > i - j + 1)min = i - j + 1;
		}
	}
	if (min != 100001)printf("%d", min);
	else printf("0");
	return 0;
}

3. 후기

자주 기출되는 만큼 복습 철저히 하기.