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

 

백준 온라인 저지(BOJ) 1806번 부분합

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

1806번: 부분합

* 사용언어 : C언어, C++

 

1. 문제

N개 자연수 수열에서 연속된 수들의 부분합이 S 이상이 되는 것 중 가장 짧은 길이 출력

 

2. 풀이

투 포인터 개념을 이해하시면 풀 수 있는 문제입니다.

 

문제의 목적이 S 이상이 되는 가장 짧은 길이를 찾는 문제이므로,

low, high 라는 2개의 포인터로 부분합의 시작과 끝을 아래 조건에 따라 하나씩 늘려가면서 길이를 찾으면 됩니다.

 

조건 1) 현재 부분합(low~high sum)이 S 보다 작은 경우

 - high 를 오른쪽으로 한 칸 이동하고 sum 에 arr[high] 값을 더해준다.

 

조건 2) 현재 부분합(low~high sum)이 S 보다 크거나 같은 경우

 - 현재 len 값과 현재 부분합의 길이(high - low + 1)를 비교하여 작은 값을 len 에 기록한다.

 - 다음 탐색을 위해 sum 에서 arr[low] 값을 빼주고 low 를 오른쪽으로 한 칸 이동한다.

 

 

while 문은 아래 2가지 조건을 만족하는 동안 반복합니다.

 

반복 1) low 가 high 보다 작거나 같은 경우

 - 수열 중 1개의 숫자만으로 S 이상이 되면, 다음 반복 시 low 가 high 보다 커지게 됩니다.

 - low 가 더 커진 경우 최소 길이는 1이고 더 이상 탐색할 이유가 없으므로 반복하지 않습니다.

 

반복 2) high 가 N 보다 작은 경우

 - high 가 N 에 도달했다는 것은 현재 sum 이 S 보다 작은 상태로 끝까지 도달한 것 입니다.

 - sum 을 더 크게 만들 수 있는 방법이 없으므로 더 이상 반복하지 않습니다.

 

3. 코드

#include <stdio.h>

#define MAX_ARR 100000
#define min(x,y) x < y ? x : y

int main() {
	int n, s;
	int arr[MAX_ARR];
	scanf("%d %d", &n, &s);
	for (int i = 0; i < n; ++i) {
		scanf("%d ", &arr[i]);
	}

	int low = 0;
	int high = 0;
	int sum = arr[0];
	int len = n + 1;

	while (low <= high && high < n) {
		if (sum < s) {
			sum += arr[++high];
		}
		else {
			len = min(len, high - low + 1);
			sum -= arr[low++];
		}
	}

	if (len == n + 1) len = 0;
	printf("%d\n", len);

	return 0;
}