[백준문제풀이] 1806 부분합

 

풀이일시 : 2020-12-24

​

문제 :

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

​

​

입력 :

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

ex)

10 15

5 1 3 5 10 7 4 9 2 8

​

​

출력 :

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

ex)

2

​

​

풀이 :

​

1. 일반 BP로 풀기 (시간초과)

시작점을 [0~N)까지 하나씩 올리며 모든 경우의 수를 따져본다.

O(N^2)가 되어 시간초과

#include <iostream>

using namespace std;
const int MAX = 100001;

int N, S;
int arr[MAX];
int startidx,realstart = 0;
int sum=0;
int result=0;
int resMIN=100001;

void input() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
}

void solution() {
	for (int i = 0; i < N; i++) { //시작점을 하나씩 올려준다.
		realstart = i;
		startidx = i;
		sum = 0;
		while (1) {
			if (realstart ==N || startidx == N) {//시작점이 선넘으면
				break;
			}
			sum += arr[startidx];
			if (sum >= S) {
				result = startidx - realstart+1;
				if (result < resMIN)
					resMIN = result;
				break;
			}
			startidx++;
		}
	}
}

int main() {
	input();
	solution();
	if (resMIN == 100001)
		resMIN = 0;
	cout << resMIN << endl;
}
​

 

2. Two pointer 로 풀기

#include <iostream>
#include <algorithm> //min 을 사용하기 위해 추가
using namespace std;

const int MAX = 100000;
const int INF = 987654321;

int arr[MAX];

int main() {

	int N, S;
	cin >> N >> S;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	int left = 0, right = 0; //포인터 두 개의 시작점
	int sum = arr[0]; //0번째 인덱스의 값으로 초기화하고 시작해보자. sum=0으로 잡을수도있음
	int result = INF; //MIN을 찾는거니 INF로 초기화해준다.

	while (left <= right && right < N) {
		if (sum < S)
			sum += arr[++right];
		else if (sum == S) { //sum과 같다면
			result = min(result, (right - left + 1)); //result설정
			sum += arr[++right]; 
		}
		else if (sum > S) {
			result = min(result, (right - left + 1));
			sum -= arr[left++];
		}
	}
	if (result == INF)
		cout << 0 << "\n";
	else
		cout << result << "\n";
	return 0;
}

 

참고자료 : Two pointer alogorithm

dbstndi6316.tistory.com/39

[개념정리] Two pointer algorithm